Dijkstra's Shortest Path Algorithm with step-by-step execution Fernando Michel Tavera Student at National Autonomous University of Mexico (UNAM) Mexico e-mail: fernando_michel@ciencias.unam.mx Social service project director: Dr. Patricia Esperanza Balderas Ca\303\261as Full time professor at National Autonomous University of Mexico (UNAM) Mexico e-mail: balderas.patricia@gmail.com
<Text-field style="Heading 1" layout="Heading 1">Introduction</Text-field> Dijkstra's Shortest Path Algorithm is a well known solution to the Shortest Paths problem, which consists in finding the shortest path (in terms of arc weights) from an initial vertex r to each other vertex in a directed weighted graph with nonnegative weights In this work we utilize the definition of the Dijkstra's algorithm given by Cook et. al. (see References) which is as follows: "Initialize y, p; set S = V; While S \342\211\240 \342\210\205 Choose v \342\210\210S with y(v) minimum; Delete v form S; Scan v." where: y is a set of y(v), the size of the shortest path found so far from r to v, for each vertex v; p is a set of the 'parent vertex' p(v)of each vertex v, that is to say the vertex prior to v in the shortest path from r to v found so far; Initialize means setting y(v) = \342\210\236 and p(v) = null for each for each vertex v except r, and y(r) = 0 (the value of p(r) is not important); S is a set of vertices that have not yet been scanned, and V is the set of all the vertices in the graph; Scanning a vertex u means verifying, for every arc a=(u,v) with weight w, that y(u) + w \342\211\245 y(v) (that is a is "correct"), and otherwise correct it. Correcting an arc a=(u,v) means changing the value of y(v) to y(u) + w such that a becomes correct, and setting p(v) = u in the process; This work is part of a social service project consisting in the implementation of several graph theory algorithms with step-by-step execution, intended to be used as a teaching aid in graph theory related courses. The usage examples presented were randomly generated.
<Text-field style="Heading 1" layout="Heading 1">Module usage</Text-field> The DijkstraSP module contains only a single procedure definition for Dijkstra(G, initial, stepByStep, draw), as follows: Calling Dijkstra(...) will attempt to calculate the shortest paths in graph G from initial to every other vertex using Dijkstra's Algorithm. The parameters taken by procedure Dijkstra(...) are explained below: G is an object of type Graph from Maple's GraphTheory library, it is the graph for which the shortest paths will be computed. G must be defined as directed and have nonnegative arc weights, otherwise the procedure will terminate with an error. This parameter is not optional initial is a symbol representing the vertex of G from which the shortest paths will be calculated. If the given symbol is not in the vertex list of G, the procedure will terminate reporting an error, otherwise the vertex of G with a label matching the given symbol will be used as initial. This parameter is not optional. stepByStep is a true/false value. When it is set to true, the procedure will print a message reporting whenever an arc is corrected or a vertex is scanned. When it is false, only the final result will be shown. This parameter is optional, and its default value is false. draw is a true/false value. When it is set to true, the resulting shortest paths graph will be displayed after computation finishes; if both stepByStep and draw are true then the graph G will be drawn at every step, highlighting arcs currently in a shortest path in green, replaced arcs in red, and scanned vertices in cyan. When draw is set to false, the graphs will not be displayed, and the procedure will print a list containing the shortest paths to each vertex, in the format: [[v1,[route to v1],distance to v1],[v2,[route to v2],distance to v2],...,[vn,[route to vn],distance to vn]] This parameter is optional, and its default value is true. The return value can be one of three possibilities as follows: If draw is true, the procedure returns a subgraph H of G containing only the arcs of G which are used in a shortest path. If draw is false, the procedure will return a list containing the shortest paths to each vertex, this is so the value reported by Maple contains more useful information. If initial is a symbol not present in the vertex list of G, G is not a directed graph, G has negative weight arcs, or there are vertices unreachable from initial, the procedure will return the string "ERROR".