Partial All Pairs Shortest Paths

5
votes

Given an undirected weighted graph which contains many nodes, how to compute a subset of the all pairs shortest path?

A subset means some of the nodes in graph, not all of them(The subset of vertices of the graph, may be appointed manually, or from some clustering algorithm. The count of the selected vertices may be 1%~5% of the total vertices).

Either Dijkstra or Floyd-Warshall may compute extra nodes, which may not be efficient enough for my application.

Is there algorithms which compute all pair shortest path between specific nodes and result good performance?

1
algorithmgraph
Which subset? - user2357112 supports Monica
not a good place for solving assignment :P - Sazzad Hissain Khan
@SazzadHissainKhan, I'm not quit understand what your are saying. But this is a challenging algorithm problem, right? And I'm not specialized in algorithm and it is normal that i can't solve it. And you known in small companies programmers are always doing every kind of works while developing. So ask problems publicly does reasonable. I hope you can understand. - My_Cat_Jessica
What is the typical size of the graph ? If it is really big, then n/100 should be considered Theta(n), and you should use Floyd-Warshall or something like that. If it is rather small (n<=1000 or so), and n/100 ends up being considered as a constant, then I don't think you can do really better than Dijkstra several times... In between (which is rather vague, I agree) lies the complicated part... - gdelab

1 Answers

0
votes

Basically, I don't think you could just consider some nodes because the shortest path in the subgraph may not be globally shortest. So you have to consider all the nodes.

Maybe you can implement the Dijkstra's algorithm like this: set a check subroutine in each iteration. if all the needed nodes have been fixed (the minimum paths have been found) terminate the algorithm. This will save time for the rest nodes.

For efficiency, I recommend use n times Dijkstra's algorithm if there are no negative edge lengths. If there are, use Johnson's algorithm, which offers a special reweighting technique to convert negative edge lengths into non-negative ones.

Maybe you just need a faster server.

Hope that helps.