Warshall’s APSP using BGL

I have been working on pgRouting for past few days, specifically the All Pairs Shortest Path APSP function. pgRouting internally uses Boost Graph Library(BGL) to handle the non-trivial graph related functionality and for APSP, we have decided to use the Warshall’s Algorithm.

The BGL manual gives an example of the Johnson’s APSP implementation, and you need to tweak it a little bit to get the same working for Warshall. The following code will give a quick bite of how you can implement the Warshall’s Algo.

Note: All credits to the BGL manual, I have just modified it to work for Warshall 🙂

#include <boost/config.hpp>

#include <iostream>

#include <fstream>
#include <boost/graph/graph_traits.hpp>

#include <boost/graph/adjacency_list.hpp>

#include <boost/graph/floyd_warshall_shortest.hpp>

using namespace boost;
typedef adjacency_list<vecS, vecS, directedS, no_property,property<edge_weight_t, int, property<edge_weight2_t, int> > > Graph;

void static_warshall()

{

const int V = 6;	typedef std::pair<int,int> Edge;
Edge edge_array[ ] =	{ Edge(0,1), Edge(0,2), Edge(0,3), Edge(0,4), Edge(0,5),	Edge(1,2), Edge(1,5), Edge(1,3), Edge(2,4),                             Edge(2,5),	Edge(3,2), Edge(4,3), Edge(4,1), Edge(5,4) };
const int E = sizeof (edge_array)/sizeof (Edge);
int weights[] = { 0, 0, 0, 0, 0, 3, -4, 8, 1, 7, 4, -5, 2, 6 };

Graph g(edge_array, edge_array + E, weights, V);

std::vector<int> d(V, std::numeric_limits<int>::max());	int D[V][V];
floyd_warshall_all_pairs_shortest_paths(g, D, distance_map(&d[0]));

for(int i=0;i<V;i++)

{

for(int j=0;j<V;j++)

{

std::cout<<D[i][j]<<" ";

}

std::cout<<std::endl;

}

}

&nbsp;

I hope I can come up with a working version of APSP for pgRouting some time in future. You can check out the core source code from the git repository I have forked here: https://github.com/jay-mahadeokar/pgrouting

Cheers!