Checking Shortest Paths

Shortest path algorithms can be complicated. How can we check that they are correct?

Luckily, there are simple and efficient algorithms to verify that the output of a single source shortest path algorithm is correct. Your task in this part of the assignment is to implement such an algorithm. You will then use this algorithm to check that your single source shortest path algorithm in part $3$ is correct!

Background

For this part all graphs will be directed and weighted, and can possibly have negative weights. We will use the graph class from Week $10$ Tutorial with the additions that now the class is templated and we add public member functions to remove edges and check if an edge is present. The template type T represents the type of the edge weights. For us$,$ T can be int, MyInteger, or double. All the functions you write will also be templated.

If an algorithm claims that the shortest path in a graph

$$

G from vertex $0$ to vertex $5$ has length $20,$ we need to verify two things:

$1)$ There actually is a path from vertex $0$ to vertex $5$ of length $20.$

$2)$ There is no path from vertex $0$ to vertex $5$ of length $<20.$

Item $(1)$ is relatively simple to verify, but $(2)$ is much more interesting. The way we will verify $(1)$ is through a shortest path tree, which we discuss next.

Shortest Path Trees

In part $3$ of this assignment you will write a single source shortest path algorithm that outputs a shortest path tree. A shortest path tree for a graph G with N vertices is a graph with only $($at most$)$ N$-1$ edges that has all the information to construct a shortest path from the source to any vertex in G$.$ The source vertex is the root of the tree, i$.$e$.,$ all edges are directed away from the source. Technically a shortest path tree is not necessarily a tree, because in the original graph G some vertices may not be reachable from the source. In the shortest path tree such non$-$reachable vertices will be isolated vertices$--$vertices no incoming or outgoing edges. Precisely, a shortest path tree will have the following properties:

a$)$ It is a tree plus some isolated vertices. Any vertex not reachable from the source must be isolated, there are no cycles even ignoring edge directions, and all edges are directed away from the root.

b$)$ All edges of the tree are also edges in the original graph, with the same weight. That is$,$ the tree is a subgraph of the original graph.

c$)$ The length of the $($unique$!)$ path from the root of the tree to any other non$-$isolated vertex is the same as the length of a shortest path in the original graph from the source to that vertex.

You will write functions to verify each of these three properties.

To check $($a$)$ we have the function

template

bool isTreePlusIsolated$($const Graph& G$,$ int root$)$;

This function should return false if and only if G contains a cycle when edge directions are ignored, or if there is a non$-$isolated vertex which is not reachable from the root.

To check $($b$)$ we have the function

template

bool isSubgraph$($const Graph& H$,$ const Graph& G$)$;

As this function is pretty simple, we generalise it beyond trees to two graphs H and G$.$ The function should return true if and only if H is a subgraph of G$,$ that is the size of H is at most that of G and every edge of H is also an edge in G with the same weight.

To help verify $($c$)$ we have a function that returns a vector that records the length of the path from the root to every other vertex in the tree.

template

std::vector pathLengthsFromRoot$($const Graph& tree, int root$)$;

As we are using this to check a "more complicated" shortest path algorithm, you should take advantage of the fact that this is a tree to use a "simple" algorithm $($hint: depth or breadth$-$first search$).$

Taken together, these functions can verify part $1$ because they show there is a path in the tree from the source to a given vertex of a certain length, and all edges of the tree are also edges in the original graph. Now let us turn to $(2).$

No shorter paths

Item $(2)$ is quite interesting. How can we verify there is no shorter path without trying all of them? All the shortest path algorithms we have studied are based on relaxing edges. We maintain a vector bestDistanceTo, where bestDistanceTo.at$($v$)$ is always an upper bound on the length of a shortest path from the source to v$.$ We then go over edges in some order and relax them. If there is an edge from u to v we do:

if $($bestDistanceTo$.$at$($u$)>$ bestDistanceTo$($v$)+$ G$.$getEdgeWeight$($v$,$ u$)\{$

bestDistanceTo.at$($u$)=$ bestDistanceTo$($v$)+$ G$.$getEdgeWeight$($v$,$ u$)$

$\}$

Think about the Bellman$-$Ford shortest path algorithm. We initialise bestDistanceTo.at$($source$)=0$ and bestDistanceTo.at$($v$)=$ infinity for every other vertex v$.$ Thus bestDistanceTo.at$($v$)$ starts as an upper bound on the distance from vertex $0$ to vertex v$.$ We then do n$-1$ rounds of relaxing every edge, when the graph has n vertice