Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

All-Pairs Source Shortest Path

In this section we consider the all-pairs, shortest path problem: Given an edge-weighted graph tex2html_wrap_inline71355, for each pair of vertices in tex2html_wrap_inline71357 find the length of the shortest weighted path between the two vertices.

One way to solve this problem is to run Dijkstra's algorithm tex2html_wrap_inline71781 times in turn using each vertex in tex2html_wrap_inline71357 as the initial vertex. Therefore, we can solve the all-pairs problem in tex2html_wrap_inline72661 time when adjacency lists are used, and tex2html_wrap_inline72663, when adjacency matrices are used. However, for a dense graph ( tex2html_wrap_inline71755) the running time of Dijkstra's algorithm is tex2html_wrap_inline72667, regardless of the representation scheme used.




next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.