Floyd Warshall using adjacency lists

问题:

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.

回答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.

回答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.