3. Connected Components and Minimum Paths
Charles M. Rader · Society for Industrial and Applied Mathematics eBooks · 2011
A familiarity with matrix algebra is useful in understanding and inventing graph algorithms. In this chapter, two very different examples of graph algorithms based on linear algebra are presented. Strongly connected components are obtained via efficient computation of infinite powers of the adjacency matrix. Shortest paths are computed using a modification of matrix exponentiation.