1

I'm trying to find all the shortest paths between pair of vertices using Floyd-Warshall algorithm. But, in the original Floyd-Warshall algorithm, it determines only one shortest path between a pair of vertices, but for my problem, I want to calculate all shortest paths (i.e., equi-weighted paths) between every vertex pair.

Based on some earlier answers, I've managed to write the C++ code as follows:

#include<set>
#include<vector>
#include<map>
#include<array>
#include<algorithm>

using namespace std;

typedef vector<vector<set<int> > > fl;

fl fw(int n, vector<array<float,4>> edge)
{
    vector<vector<float> > cost(n);
    vector<vector<set<int> > > next_node(n);

    for(int i=0;i<n;i++)
    {
        next_node[i]=vector<set<int> >(n);
        cost[i]=vector<float>(n,INT_MAX);
        cost[i][i]=0;
    }

    for(auto &i:edge)
    {
        if(i[2]<cost[i[0]][i[1]])
        {
                cost[i[0]][i[1]]=i[2];
                next_node[i[0]][i[1]]=set<int>{i[1]};
        }
        else if(i[2]==cost[i[0]][i[1]] && i[0]<INT_MAX)
        {
            (next_node[i[0]][i[1]]).insert(i[1]);
        }

    }

    for(int k=0;k<n;k++)
    {
        for(int i=0;i<n;i++)
        {

            for(int j=0;j<n;j++)
            {

                float cost_ik_kj = cost[i][k]+cost[k][j];

                if(cost_ik_kj < cost[i][j])
                {
                    cost[i][j]=cost_ik_kj;
                    next_node[i][j]=set<int>{next_node[i][k]};
                }
                else if(cost_ik_kj==cost[i][j] && cost_ik_kj<MAX)
                {
                    (next_node[i][j]).insert((next_node[i][k]).begin(),(next_node[i][k]).end())
                }

            }
        }
    }
return next_node;
}

But after returning the next_node vector, I'm unsure of how to reconstruct the path from it in C++11. What will be the path_reconstruction function for the same? The input edge to fw function is in the edge-list format i.e.,

vector<vector<float>> edge{{0,2,2},{2,3,2},{3,1,1},{1,0,4},{1,2,3},{0,3,4},{3,0,5}};

For reference: I used the below Python code as reference for writing in above C++ code.

def floyd_warshall(n, edge):
    rn = range(n)
    cost = [[inf] * n for i in rn]
    next_node = [[set() for j in rn] for i in rn]

    for i in rn:
        cost[i][i] = 0

    for u, v, w in edge:
        # The data format allows multiple edges between two nodes.
        if w < cost[u][v]:
            cost[u][v] = w
            next_node[u][v] = set([v])
        elif w == cost[u][v] and w < inf:
            next_node[u][v].add(v)

    for k in rn:
        for i in rn:
            for j in rn:
                cost_ik_kj = cost[i][k] + cost[k][j]
                if cost_ik_kj < cost[i][j]:
                    cost[i][j] = cost_ik_kj
                    next_node[i][j] = set(next_node[i][k]) # Want a copy.
                elif cost_ik_kj == cost[i][j] and cost_ik_kj < inf:
                    next_node[i][j].update( next_node[i][k] )

    return next_node

The path reconstruction function using next_nodes is an iterator function all_paths:

def all_paths(next_node, i, j):
    if 0 == len(next_node[i][j]):
        if i == j:
            yield [j]
        else:
            pass # There is no path.
    else:
        for k in next_node[i][j]:
            for rest in all_paths(next_node, k, j):
                yield [i] + rest


edge = [[0,2,2],[2,3,2],[3,1,1],[1,0,4],[1,2,3],[0,3,4],[3,0,5]]
# Here n is the value of the highest numbered-vertex. In the above graph, n=4
n=4
next_node = floyd_warshall(n,edge)
for i in range(4):
    for j in range(4):
        for path in all_paths(next_node, i, j):
            print((i, j, path))

Edited: If there is a better way of doing it, it's quite welcome :)

Plax
  • 23
  • 4

0 Answers0