Finding the shortest route using Dijkstra algorithm

Question

I need to find the shortest route between 2 vertices of a graph. I have a matrix, which contains all the weights. How can I do it? Currently, I have the following code:

private int[] Dijkstra(int start, int end)
    {
        bool[] done = new bool[8];
        int[] parent = new int[8];
        for (int i = 0; i < parent.Length; i++)
            parent[i] = -1;
        int[] distances = new int[8];
        for (int i = 0; i < distances.Length; i++)
            distances[i] = int.MaxValue;
        distances[start] = 0;
        int current = start;
        while (!done[current])
        {
            done[current] = true;
            for (int i = 0; i < 8; i++)
            {
                if (graph[current, i] != int.MaxValue)
                {
                    int dist = graph[current, i] + distances[current];
                    if (dist < distances[i])
                    {
                        distances[i] = dist;
                        parent[i] = current;
                    }
                }
            }
            int min = int.MaxValue;
            for (int i = 0; i < 8; i++)
            {
                if (distances[i] < min&&!done[i])
                {
                    current = i;
                    min = distances[i];
                }
            }
        }
        return parent;
    }

It works, but, however I don't know how to make it find the shortest route between, for example 1 and 3, and return the route like 1=>4=>2=>3.
Thanks in advance.

Answer 1

Djikstra's Algorithm uses the parent array to track the shortest path from start to end. You'd start at parent[end] and follow the entries of the array until you got back to start.

Some pseudocode:

List<int> shortestPath = new List<int>();
int current = end;
while( current != start ) {
     shortestPath.Add( current );
     current = parent[current];
}

shortestPath.Reverse();

Only thing you worry have to worry about with your function is whether or not the start and end values passed in are appropriate values (whether or not they actually represent vertices in your graph, for example ).