Finding all shortest paths and distances using Floyd-Warshall

Question

First, a little background: I'm working on building a simple graph class with basic graph algorithms (Dijkstra, Floyd-Warshall, Bellman-Ford, etc) to use as a reference sheet for an upcoming programing competition.

So far I have a functioning version of Floyd-Warshall, but the downside is that so far it's only getting me the shortest distance value between two nodes, not the shortest path. Preferably I'd like to have the path-building take place within the algorithm itself instead of having to call another function to reconstruct it.

Here's some info on the data structures I'm using:

vector< vector<int> > graph //contains the distance values from each node to each other node (graph[1][3] contains the length of the edge from node #1 to node #3, if no edge, the value is INF

vector< vector<int> > path //contains the "stepping stones" on how to reach a given node. path[st_node][end_node] contains the value of the next node on the way from end_node -> st_node

Here's the example graph data I'm using:

INF 10  INF INF INF INF
INF INF 90  15  INF INF
INF INF INF INF INF 20
INF INF INF INF 20  INF
INF INF  5  INF INF INF
INF INF INF INF INF INF

and here's the desired values to be in the "path" variable (gotten by running Dijkstra from each of the nodes):

INF  0   4   1   3   2
INF INF  4   1   3   2
INF INF INF INF INF  2
INF INF  4  INF  3   2
INF INF  4  INF INF  2
INF INF INF INF INF INF

Here's a link to the code I'm currently using for the algorithm: (via PasteBin).

Any help would be greatly appreciated!

Edit: I tried Wikipedia's code to generate the path matrix and here's the result:

INF INF  4   1   3   4
INF INF  4  INF  3   4
INF INF INF INF INF INF
INF INF  4  INF INF  4
INF INF INF INF INF  2
INF INF INF INF INF INF

It kinda works but has issues when it comes to representing "single" steps. For example, the path from node 0 to node 1 is undefined everywhere. (But nonetheless, thank you Nali4Freedom for the suggestion)

Answer 1

Wikipedia has some good info and pseudocode. Basically you just fill a |V|x|V| 'next' matrix where element i,j contains the index of the vertex you need to go to to get from node i to node j. The shortest path from i to j can then be gives as the path from i to next[i][j] and from next[i][j] to j. You continue to decompose the path recursively like this until you have the full path.

Answer 2

Huzzah!

I had a good hard stare at the results from adding Wikipedia's code snippet and I came up with an adapter to convert it's results into my results without the need of calling a separate function:

// Time to clean up the path graph...
for (int st_node = 0; st_node < this->size; st_node++)
{
    for (int end_node = 0; end_node < this->size; end_node++)
    {
        int mid_node = this->path[st_node][end_node];

        if (mid_node == INF)
        {
            // There is no mid_node, it's probably just a single step.
            if (this->graph[st_node][end_node] != INF)
            {
                this->path[st_node][end_node] = st_node;
            }

        } else {
            // The mid_node may be part of a multi-step, find where it leads.
            while (this->path[mid_node][end_node] != INF)
            {
                if (this->path[mid_node][end_node] == mid_node) { break; }  // Infinite loop
                if (this->path[mid_node][end_node] == INF) { break; }   // Dead end

                mid_node = this->path[mid_node][end_node];
            }

            this->path[st_node][end_node] = mid_node;

        }   // IF mid_node
    }   // FOR end_node
}   // FOR st_node

Essentially this compensates for when getting from node A to node B is a single step (mid_node == INF) by adding the edge if it existed in the original graph. Alternately, if the node it points to is just a stepping stone to the destination node (this->path[mid_node][end_node] != INF) then it digs until it finds where it leads to.

Thanks for the help guys, guess I just needed someone to think out loud to!

Answer 3

How to find the shortest path in a graph represented by vector>?