Thursday, August 18, 2011

All pairs shortest paths in unweighted graph ?

What is an efficient way to compute, for all vertices in an undirected unweighted graph, the shortest paths to all other vertices ? (Here shortest means the path with the least number of edges). The Floyd-Warshall algorithm will run in O(n^3) time, but since this graph is unweighted, can we do better ?

No comments:

Post a Comment