void Graph::writeShortestPaths (int first, ostream& outfile)
{
    for (int i = 0; i < n; i++)// each vertex
    {
        currentDistances[i] = 999999;
        predecessors[i] = -1;
        toBeChecked[i] = true;
    }

    currentDistances[first] = 0;
    writeShortestPathsHeader (outfile, first);
    int pass = 0;
    while (moreShortestPathsToFind()) // see below
    { 
        int minVertex = first; // index of closest of vertices remaining to be reached
        toBeChecked[minVertex] = false;
        for (int i = 0; i < n; i++)// each vertex i
        {
            if (distances[n * minVertex + i] != 999 && predecessors[i] == -1) // i hasn't been reached yet and it is reachable from the new minVertex
            {
                if (currentDistances[i] > distances[n * minVertex + i])// previous distance to i is larger than the distance via minVertex
                {
                    currentDistances[i] = distances[n * minVertex + i];// distance via minVertex
                    predecessors[i] = minVertex;
                    toBeChecked[minVertex] = false;
                    // cant figure out how to set First!!!! At least not without out getttng a never ending while loop
                }
            }
        }
        writeShortestPathsIntermediate (outfile, pass, minVertex);
    }
    writeShortestPathsResults (outfile);
}

I'm getting frustrated, I can do this algorithm on paper. However, I cant get it to work in code. I can't seem to figure out how to jump the the next vertex with the shortest distance. Thanks for any help.

I remember Dijkstra’s Algorithm from my layout class. Good times. I think I would change the architecture so that you use a linked list to store connections between nodes. A less elegant approach might be to store a list of connections in an array. When the connection has been checked, the linked list node would be removed, or the array element would be set to zero. In either case, I would not worry about which intermediate distance is the shortest until a full path has been found. For example, if you find one path that is 3 + 5+ 4 + 10, and you check one path that has 30 as the first distance, you would immediately stop checking that path, and would delete that linked list head, or set the array to zero. Good luck.

I remember Dijkstra’s Algorithm from my layout class. Good times. I think I would change the architecture so that you use a linked list to store connections between nodes. A less elegant approach might be to store a list of connections in an array. When the connection has been checked, the linked list node would be removed, or the array element would be set to zero. In either case, I would not worry about which intermediate distance is the shortest until a full path has been found. For example, if you find one path that is 3 + 5+ 4 + 10, and you check one path that has 30 as the first distance, you would immediately stop checking that path, and would delete that linked list head, or set the array to zero. Good luck.

I would love to do that it seems much more natural to do it that way. However, that isn't how our professor wants us to do it.
I have figure out that my problem isn't jumping to the next shortest vertex. It does that, I just cant figure out how to get it to jump back if the vertex points to nowhere.

This article has been dead for over six months. Start a new discussion instead.