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)

If I'm reading this right, according to the first row of graph there's only one edge from node #0, and it leads to node #1. So the first row (or maybe first column) of path should be Inf 1 1 1 1 1. What am I missing? — Beta
Ah, I see how you could get confused with that yes. Each row in graph lists the edges leaving from that node whereas each row in path contains the path to get to node #[row_num]. For example, the first row of the correct path chart means that to get to node 0 (row = 0) from node 5 (col = 5), the next node on the way back is node 2. To get to node 0 from node 2 we use node 4, then node 3, then node 1, then finally at our destination with node 0. — Mr. Llama

Mr. Llama Mr. Llama · Accepted Answer · 2010-10-25T22:39:06

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!

Finding all shortest paths and distances using Floyd-Warshall

2 Answers