ABSTRACT
This chapter discusses a method for finding a shortest route within a graph. In addition, a method for determining a work schedule for various interdependent processes provides another application of routes within a digraph. Numerous versions of Dijkstra's Algorithm exist, though two basic descriptions adhere to Dijkstra's original design. In one, the shortest paths from one chosen vertex to all other vertices are found. The chapter focuses on finding a specific path within a graph, but the authors are no longer interested in the shortest path. Instead, one will be searching for a critical path within a graph representing multiple interdependent pieces of a project. Perhaps more surprising is how important this algorithm would become to modern society — almost every Geographic Information System (GIS), or mapping software uses a modification of Dijkstra's algorithm to provide directions. In addition, Dijkstra's algorithm provides the backbone of many routing systems and some studies in epidemiology.
