Path Problems in Directed Graphs 

The weight of an edge in a directed graph is often thought of as its length. The length of a path <v_{0}, v_{1}, ..., v_{n}> is the sum of the lengths of all component edges <v_{i},v_{i+1}>. Finding the shortest paths between vertices in a graph is an important class of problem. Single Source Shortest Paths in a Directed Graph
As an example of a path problem, the firebrigade keeps a map of the city marked with the locations of especially hazardous sites, such as chemical stores. They wish to know the shortest route from the firestation to each site. Note the "length" of a road might be either its physical length or the estimated driving time on it, which are not necessarily proportional to each other. It turns out that it as easy to find the shortest paths from
a single source to all other vertices
as it is to find the shortest path between any two vertices.
Usually the source is taken to be v_{1}.
Dijkstra's
algorithm solves this singlesource shortest paths problem
in O(V^{2}) time.
It operates by enlarging the set of vertices `done' for which the
shortest paths from the source are known.
Initially done contains just the source v_{1}.
At an intermediate stage,
the vertex not in the set done that is closest to the source
is found and added to done.
This allows our knowledge of the shortest paths to the remaining vertices in
 Graph G = <V, E>  P[i] is the best (known) path length  from source to vertex i done := {v_{1}} for vertex i in V{1} P[i] := E[1,i] direct edges end for loop V1 times find closest vertex to v_{1} in V  done done +:= {closest} for vertex j in V  done P[j]:=min(P[j], update knowledge on shortest paths, P[closest]+E[closest,j]) perhaps better? end for end loop  Dijkstra's SingleSource Shortest Paths Algorithm Initially P reflects the direct edges from the source. On the first iteration of the main loop, the vertex with the shortest direct connection from the source is chosen. This is correct because any indirect path to this vertex would have to leave the source by an edge at least as long. Once a closest vertex is chosen to add to done, it may give knowledge of shorter paths from the source, via closest, to other as yet unchosen vertices. The algorithm follows what is known as a greedy strategy. It adds vertices to done as cheaply as possible. The strategy is often a good heuristic; in this problem it also gives a correct algorithm. As given, the algorithm calculates the lengths of the shorest paths from the source to each other vertex. If it is necessary to find the paths themselves, note that the algorithm traces a rooted tree with the source as the root. When the vector of path lengths is updated, if P(j) is reduced by the `min' then `closest' can be associated with j in another vector. This allows the paths to be recovered, in a reverse direction. CorrectnessThe algorithm is correct because of a property of shortest paths:
If This property of shortest paths, and its use here, is an example of dynamic programming. ComplexityThe algorithm contains an outer loop executed V1 times and inner loops, to find the closest vertex and update distances, executed O(V) times for each iteration of the outer loop. Its timecomplexity is therefore O(V^{2}). All Pairs Shortest Paths in a Directed GraphFloyd's algorithm calculates the costs of the shortest path between each pair of vertices in O(V^{3}) time. It consists of three nested loops. The invariant of the outer loop is the key to the algorithm. At the start of an iteration, P holds the optimal path length from v_{i} to v_{j}, for each i and j, considering only paths that go direct or via vertices v_{n} for n<k. This is certainly true initially when k=1 and P holds only direct paths. At each iteration the next value of k is considered. There may now be a better path possible from v_{i} to v_{j} via this new v_{k}, but note that it will visit v_{k} at most once. This means it is sufficient to consider paths from v_{i} to v_{k} possibly via {v_{1}, ..., v_{k1}} and then on from v_{k} to v_{j} also possibly via {v_{1}, ..., v_{k1}}. Thus the invariant is maintained. Finally P holds optimal path lengths for unrestricted paths.
CorrectnessThe invariant in the code is the key to the algorithm's correctness.
At the start of the k^{th} iteration of the outer loop,
F[,] contains the lengths of the shortest paths from
v_{i} to v_{j},
possibly via intermediate vertices in the set
ComplexityWith three nested loops, Floyd's algorithm runs in O(V^{3})time. Running Dijkstra's single source algorithm V times with each vertex as the source in turn also finds all shortest paths in O(V^{3}) time but Floyd's algorithm is more direct. Connectedness and Transitive ClosureRecall that vertices v_{i} and v_{j} are adjacent in a graph G if there is an edge <v_{i},v_{j}>. This information can be stored in a Boolean adjacency matrix A. v_{i} and v_{j} are said to be connected if there is a path from v_{i} to v_{j}. A variation on Floyd's algorithm calculates connectivity. This is Warshall's algorithm which was actually discovered first. Omitting the checks for missing edges, the central operation in Floyd's algorithm is:
The notion of closure can be extended to more general operations, f and g provided that
(Exercise: verify that these pairs <f,g> satisfy the requirements.) CorrectnessCorrectness follows from the same argument used above for Floyd's algorithm. ComplexityThe timecomplexity of Warshall's algorithm is O(V^{3}), as for Floyd's algorithm. DemonstrationThe HTML FORM
below allows a random
edgeweighted, directed graph
with V vertices to be created, manipulated and analysed.
The value `pr' is the probability of there being an edge <i,j>;
it controls the sparseness of the graph
and on average there will be pr*V*(V1) edges:
Notes


↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso88591, fetched Wednesday, 11Dec2019 03:01:29 EST. Free: Linux, Ubuntu operatingsys, OpenOffice officesuite, The GIMP ~photoshop, Firefox webbrowser, FlashBlock flash on/off. 