Chapter 4. Pathway problems

This chapter is devoted to the study of pathway problems in graph theory, which consist of determining specific structures or properties within a graph by following its vertices and edges according to well-defined rules. These problems are fundamental in various applications such as network design, communication systems, transportation, and optimization.

In the first section, we focus on the search for connected components, which aims to identify all subsets of vertices where each pair of vertices is connected by a path. The Trémeaux–Tarjan algorithm is introduced as an efficient method for detecting both connected and strongly connected components in undirected and directed graphs, respectively.

The second section deals with the problem of finding the shortest path between vertices in a weighted graph. After presenting the main conditions of the problem, we describe the Moore–Dijkstra algorithm, which provides an optimal and systematic way to compute the minimum distance from a given source vertex to all others.

Finally, the third section addresses the construction of a spanning tree of maximum weight in a connected graph. The objective is to select a subset of edges that connects all vertices while maximizing the total weight. For this purpose, the Kruskal algorithm (1956) is presented as a classical and effective approach.

Through these three parts, the chapter offers a unified understanding of fundamental graph traversal and optimization techniques that form the basis of many modern computational applications.