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