Implement Dijkstra’s Algorithm in C#

This was a part of my project work done, when I was in semester 6. The project was “Routing System” was an online graphical solution, which displayed the shortest possible path between any two destinations. Well, I am not going to mention the various features which I had included in the system, rather I am giving an idea on implementation of dijkstra’s algorithm which was the central most attraction and requirement of the system.

Please refer and understand dijkstra’s algorithm before you implement it.

The implementation (source code) provided below can be used to find the smallest possible path from any node to any node:-

int startnode=-1,endnode=-1;
int count = 0;
int[,] A = new int[num_node, num_node];//main matrix
//num_node represents the number of nodes in the system.
//Assuming that the matrix A[num_node][num_node], which stores the distances between the pairs of node, is provided.
int[] C = new int[num_node];//to check if the node is visited or not.
int[] D = new int[num_node];//stores total distances between startnode and endnode through all the possible path.
string[] traverse = new string[num_node];//stores all the possible path between start node and end node.

//Dijkstra’s algorithm starts here————————————————————-
//startnode and endnode should be provided by user of the system through any input method in C#.

int minNode = startnode;
for (int i = 0; i < num_node; i++)
{
C[i] = i;
D[i] = A[minNode, i];
if (A[minNode, i] > 0)
{
traverse[i] = Convert.ToString(minNode) + “,” + Convert.ToString(i);//stores the path having direct connection
}
}

C[startnode] = -1;//marking the startnode as read by assigning it value -1

for (int k = 0; k < num_node; k++)//loop to find the next minimum node
{
int minValue = Int32.MaxValue;
for (int l = 0; l < num_node; l++)
{
if (C[l] >= 0)//check if the node is traversed before
{
if ((D[l] > 0) && (D[l] < minValue))
{
minValue = D[l];//stores the minimum value
minNode = l;//mimimum node is stored
}
}
}

C[minNode] = -1;//marking the minimum node as read by assigning its value -1
for (int m = 0; m < num_node; m++)
{
if (C[m] >= 0)//check if the node is traversed before
{
if (A[minNode, m] > 0)//checks if there is a direct connection
{
if (D[m] < 0)
{
D[m] = A[minNode, m] + minValue;
traverse[m] = traverse[minNode] + “,” + Convert.ToString(m);//stores the path
}
else if ((A[minNode, m] + minValue) < D[m])//checks if the distance is minimum
{
D[m] = A[minNode, m] + minValue;
traverse[m] = traverse[minNode] + “,” + Convert.ToString(m);//stores the path
}
}
}
}
}

” D[endnode] ” and ” traverse[endnode] “ gives the smallest distance and path between start node and end node, which can be used as per the requirement

hope this helps many…..