Floyd Warshall using adjacency lists

Question

Is is possible to code Floyd Warshall using adjacency lists? I have to process a million vertices from a text file and hence, adjacency matrices is not a solution. Any implementation already available? Please help.

Answer 1

You cant use Floyd Warshall with adjacency list because when it works, it makes new edges.

Example :

First, your graph has 2 Edges ( 1-2, 2-3 ). So you initialize the adjacency matrix :

adj[1][2] = 1; ( means have edge between 1 and 2)

adj[2][3] = 1; ( means have edge between 3 and 2)

adj[1][3] = +oo; ( means no edge between 1 and 3 )

And when FW works, edge 1-3 wil be added because adj[1][2] + adj[2][3] < adj[1][3] => adj[1][3] = 2 ( means have edge between 1 and 3 );

I dont know how many edges in your graph and time limit to solve but if you need to calculate the shortest path between all pair in graph, you can do |V| times Dijkstra with Priority queue which has complexity is |V| * max( |V|log|V| , |E| ) better than |V|^3 of Floyd Warshall.

Answer 2

Floyd Warshall Implementation using adjacency list but it internally converts the adjacency list to matrix before staring the algo. If your graph is not sparse then using adj list instead of matrix won't help because anyways you need to scan all edges. But if your graph is very sparse then you might want to consider running Dijkstra'a shortest path algo from each node instead of using Floyd Warshall. As mentioned by Anh Huynh in the other response if you definitely know that |E| ~ |V| log^k |V| where 0 <= k then running Dijkstra's algo for each node will give you better time complexity than Floyd Warshall.

Answer 3

Try to use Johnson's Algorithm (as stated by Anh Huynh and Diptendu) is very effective for sparse graphs as its time complexity is dependent on number of edges in that graph. Use Floyd Warshall's Algorithm only when graph is very dense. Choose from above algorithms according to your need.