11 Shortest Path Algorithms, Cheapest Walks in Weighted Graphs, Acyclical Graphs and Topological Sort, Dijkstra's Algorithm

Lecture from: 21.11.2024 | Rui Zhangs Notes | Video: Videos ETHZ

Graph Algorithms

Over the past two weeks, we’ve delved into graph algorithms, focusing on Eulerian walks and Topological Sorting. While distinct problems, the approaches we used to develop algorithms for these problems share some key similarities.

Common Algorithmic Approach

Both algorithms employed a strategy of iterative walk construction:

1. Iterative Construction: We built walks within the graph until a specific condition halted further progress.
2. Stopping Condition (Eulerian Walks): In the case of Eulerian walks, we continued extending the walk until encountering a situation where the only way to proceed involved traversing an edge that was already part of the walk (edge repetition).
3. Stopping Condition (Topological Sort): For topological sorting, we continued extending the walk until we reached a vertex that had already been visited. This implied the existence of a cycle in the directed graph. This was a simplified view and there are other conditions we looked at.

Key Findings and Generalizations

The algorithms for both problems enabled us to make important observations and generalizations:

Eulerian Walks

• Cycle Detection: By attempting to construct an Eulerian walk, we demonstrated that if a non-repeating walk exists (i.e., an Eulerian path), then that walk must be a cycle.
• Generalization: We broadened this observation to the general principle: if a cycle exists within the graph, then our algorithm is guaranteed to find it.

Topological Sort

• Sink Detection: In the context of topological sorting, we showed that if our constructed walk terminates at a vertex without any outgoing edges (a sink), then that vertex can be added to the topological order.
• Generalization: Here, we showed that sinks are a requirement for Toposort and when visiting new nodes, we can discover these sinks.

Summary and Connection

In both cases, our algorithms helped us identify specific structural properties of the graphs (cycles in Eulerian walks, sinks in topological sort). The presence or absence of these properties then informs us about the existence or non-existence of solutions to the respective problems. If we can find cycles, we can construct an Eulerian path. If we can find sinks, then we can build a valid topological ordering.

Road Networks and Shortest Paths

Imagine we have data representing a road network. Our goal is to find a path with the fewest intersections.

Representing this road network as a graph, we define:

• Nodes: Intersections
• Edges: Road segments between intersections

We seek the shortest walk (or path) between two given intersections. Edges may be directed, representing one-way streets. Note that we can equivalently search for the shortest path instead of the shortest walk. Any walk containing duplicate vertices implies the traversal of a cycle. Such a cycle can be eliminated to create a shorter path, as illustrated below:

This problem of finding the shortest path appears in various contexts. For example, the Edit Distance dynamic programming problem (07 Dynamic Programming, Jump Game, Longest Common Subsequence, Edit Distance) can be formulated as a graph problem.

Here, the larger, elongated nodes (those with more than three edges) represent matching subsequences. They are visually distinct because there’s no “cost” associated with matching characters. This allows us to “skip” edit operations (insertions, deletions, substitutions) when characters are already equal, effectively traversing these elongated nodes at zero cost.

Definitions

Let $d(u,v)$ denote the shortest path length (number of edges) between vertices $u$ and $v$. For simplicity, we assume each edge has a length of 1.

Breadth-First Search (BFS)

Given a graph $G=(V,E)$, a common task is to find the shortest paths from a source vertex $s$ to all other reachable vertices $v\in V$. A key insight is that computing $d(s,v)$ for all reachable $v$ is computationally similar to finding the shortest path to a single vertex. Thus, we focus on calculating $d(s,v)$ for all $v$ reachable from $s$. Breadth-First Search (BFS) provides an efficient algorithm for this purpose.

Instead of directly asking for the distance between $u$ and $v$, we consider the set of vertices reachable from $u$ at a distance $k$. In other words, we seek the set of vertices $v$ for which $d(u,v)=k$.

Consider the following graph, starting at node A:

BFS explores the graph in layers, radiating outwards from the source vertex $s$. It systematically visits all neighbors of $s$ first, then their neighbors, and so on. This layered exploration guarantees that we find the shortest paths (in terms of the number of edges) to all reachable vertices. We can disregard cycles, as any cycle would imply a longer path that we’ve already discovered a shortcut for.

The following illustration shows the distances of each vertex from A:

This structure is called a shortest path tree. It represents the shortest paths from the source vertex $s$ to all other reachable vertices. A level $k$ is defined as the set $L_k:=\{v\in V|d(s,v)=k\}$. In other words, $L_k$ contains all vertices at a distance $k$ from the source $s$.

Determining Level $k$

An edge from a vertex in $L_k$ to a vertex in $L_{k^{\prime }}$ implies that $k^{\prime }\le k+1$. This is because traversing an edge increases the distance from the source $s$ by at most 1. In an undirected graph, this relationship becomes $k-1\le k^{\prime }\le k+1$ because an edge can also lead to a vertex in the previous level.

Assume we have already computed the sets $L_0,L_1,\dots ,L_{k-1}$. How do we compute $L_k$?

A vertex $v$ belongs to $L_k$ (meaning the shortest distance from $s$ to $v$ is $k$) if and only if both of the following conditions hold:

1. Not in Previous Levels ($v\notin L_0\cup L_1\cup \cdots \cup L_{k-1}$): This condition is crucial for ensuring that we are indeed finding the shortest distance to $v$. If $v$ were already present in a level closer to $s$ (say $L_j$ where $j<k$), then $d(s,v)$ would be $j$, not $k$. We want to avoid including vertices in $L_k$ that have shorter paths.

2. Successor of a Vertex in $L_{k-1}$ ( $v$ is a neighbor of some $u\in L_{k-1}$): This condition establishes that $v$ is reachable from $s$ in exactly $k$ steps. Since every vertex in $L_{k-1}$ is at distance $k-1$ from $s$, and $v$ is a neighbor of a vertex in $L_{k-1}$, the distance from $s$ to $v$ must be $(k-1)+1=k$.

These two conditions together precisely define the set of vertices that are at distance $k$ from the source vertex $s$. Condition 1 excludes vertices that are closer to $s$, and condition 2 ensures that the vertices are reachable in exactly $k$ steps.

Algorithm Sketch

The algorithm to compute the shortest path distances from a source vertex s is as follows:

def shortest_path_distances(G, s):
    """
    Computes shortest path distances from a source vertex using BFS.
 
    Args:
        G: The graph represented as an adjacency list (dictionary).
        s: The source vertex.
 
    Returns:
        A list of sets S_0, S_1, ..., S_{n-1}, where S_k = {v | d(s, v) = k}.
    """
 
    n = len(G)  # Number of vertices
    S = [set() for _ in range(n)]  # Initialize list of sets
    S[0] = {s}
    marked = {v: False for v in G}  # Keep track of visited vertices
    marked[s] = True
 
    for k in range(1, n):
        for u in S[k-1]:
            for v in G[u]:  # Iterate through neighbors of u
                if not marked[v]:
                    S[k].add(v)
                    marked[v] = True  # Mark v as visited
    return S
 

1. Marking Nodes: Once the distance to a node is known, we mark it to avoid redundant processing. This allows constant-time checks for whether a vertex has already been assigned a distance. We use a shared data structure (e.g., a boolean array or a hash set) to store this marking information. The time complexity for this step is $O(n)$, where $n=|V|$ is the number of vertices.

2. Iterating through $S_{k-1}$: The outer loop iterates through the sets $S_{k-1}$ to process vertices at distance $k-1$. In the worst case, ${\sum }_{k=1}^{n-1}|S_{k-1}|\le n$.

3. Building $S_k$: For each vertex $u$, we iterate through its neighbors and add any unmarked neighbors to the set $S_k$. The runtime of this step depends on how efficiently we can access the neighbors of $u$. With an adjacency list representation, the total work across all iterations is proportional to the number of edges $m=|E|$. The time complexity for this step is $O(m)$.

Using an adjacency list representation for the graph, the runtime of the algorithm is $O(n+m)$ where $n=|V|$ is the number of vertices and $m=|E|$ is the number of edges. This is because each vertex and each edge are processed at most once. With an adjacency matrix, the runtime would be $O(n^2)$ because we would need to iterate through all n possible neighbors for each vertex.

Using a Queue for Efficient BFS Implementation

While the algorithm described previously correctly computes shortest path distances, its direct implementation can be inefficient. Specifically, repeatedly iterating through the sets $S_k$ to find unvisited neighbors can lead to redundant checks. A queue data structure provides a more efficient way to organize the exploration process.

A queue operates on the First-In, First-Out (FIFO) principle. Elements are added to the rear of the queue (enqueued) and removed from the front (dequeued).

Why Use a Queue?

1. Systematic Exploration: A queue ensures that we explore the graph level by level. Vertices at distance $k$ are enqueued only after all vertices at distance $k-1$ have been processed. This maintains the BFS’s layered exploration property, crucial for finding shortest paths.

2. Avoid Redundant Checks: Once a vertex is enqueued, we know its distance from the source. When we dequeue it, we process its neighbors. We enqueue each unvisited neighbor only once. This eliminates the need for the $v\notin (S_0\cup \cdots \cup S_{k-1})$ check in the previous algorithm, saving significant computation. The marking of visited vertices still prevents processing a vertex multiple times.

3. Efficient $S_k$ Construction: The queue implicitly maintains the sets Sₖ. The elements currently in the queue represent the “frontier” of exploration – vertices at the current distance being expanded.

Modified Algorithm with a Queue

from collections import deque
 
def bfs_shortest_paths(G, s):
  """Computes shortest path distances using BFS with a queue."""
  dist = {v: float('inf') for v in G}
  dist[s] = 0
  q = deque([s])  # Initialize queue with the source vertex
  parent = {} #dictionary to maintain shortest path tree
  
  while q:
    u = q.popleft()
    for v in G[u]:
        if dist[v] == float('inf'):
          dist[v] = dist[u] + 1
          parent[v] = u # u is parent of v
          q.append(v)
  return dist, parent # return distances and the shortest path tree

Runtime Analysis with a Queue

The queue-based BFS algorithm maintains the same $\mathcal{O}(|V|+|E|)$ time complexity as the previous version but is more efficient in practice due to:

• Constant-time Enqueue/Dequeue: Queue operations take constant time, ensuring efficient addition and removal of vertices.
• No Set Operations: Eliminating the need for set union operations ($v\notin (S_0\cup \cdots \cup S_{k-1})$) significantly reduces overhead, especially for dense graphs. Only constant time checks for already visited vertices remain necessary.

The use of a queue drastically improves the practical efficiency of BFS, making it the preferred method for computing shortest paths in unweighted graphs. The parent dictionary returned alongside the dist dictionary can be used to efficiently reconstruct the actual shortest path from the source s to any reachable vertex.

BFS: Enter and Leave Times

The concept of enter and leave times provides valuable insights into the execution and properties of the Breadth-First Search (BFS) algorithm. These timestamps, associated with each vertex, capture the order in which vertices are first encountered (entered) and finished processing (left) during the BFS traversal.

Definitions and Notations

• enter[v]: The time (or step) at which vertex $v$ is first encountered and added to the queue.
• leave[v]: The time at which vertex $v$ is dequeued and its neighbors are processed.
• T: A global counter representing the current time step. It is initialized to 1 and incremented each time a vertex is entered or left.

We can now visualize the intervals:

Observations

Part of the notes, wasn’t looked at in the lecture…

1. enter[v] < leave[v]: A vertex is always entered before it is left. This is a fundamental property of the BFS traversal since each vertex is visited and processed in a single operation once it is dequeued.

2. enter-order = leave-order (within levels): Within a given level $L_k$ (vertices at distance k from the source), the enter times and leave times respect the same relative ordering. If a vertex u is entered before vertex v in the same level, it will also be left before v. This is due to the FIFO nature of the queue and the layered exploration strategy of BFS. However, this is not true across different levels, where vertices with larger distances will have both enter and leave times larger than close-by vertices.

3. Epochs and $R_k$: The interval $[t_k,t_{k+1})$ defines an epoch during the BFS execution. $t_k$ is the time when the first vertex at distance $k$ is dequeued (and left). $t_{k+1}$ signifies the end of level $k$ exploration, and the beginning of level $k+1$ or the completion of the BFS traversal if no vertices at level $k+1$ exist. $R_k$, the set of vertices left in the interval $[t_k,t_{k+1})$, is equivalent to the set $L_k$.

Justification and Proof

Part of the notes, wasn’t looked at in the lecture…

The core idea is to prove that the set of vertices $S_k$ (at distance k from the source) is equivalent to the set $R_k$ (vertices with leave times in the interval $[t_k,t_{k+1})$). Formally:

$\forall k\in {\mathbb{N}}_0:S_k=R_k=\{v|t_k\le \text{leave}[v]<t_{k+1}\}$

where $t_k=\min \{\text{leave}[v]|d(s,v)=k\}$.

We want to show that the set of vertices at distance $k$ from the source ($S_k$) is identical to the set of vertices whose leave times fall within the interval $[t_k,t_{k+1})$ ($R_k$). Here, $t_k$ is the time the first vertex at distance $k$ is dequeued. This means that the vertices in $R_k$ are precisely those dequeued between the start of processing level $k$ and the start of processing level $k+1$.

1. Key Idea: BFS explores the graph layer by layer. The queue always contains vertices from the current level and the next. Once a level is completely processed, all vertices at that level have left the queue.

2. Base Case ($k=0$):

The source vertex $s$ is at distance 0 ($S_0=\{s\}$). It’s the first vertex enqueued and dequeued. Thus, its leave time is $t_0=1$, and $R_0=\{s\}$. Therefore, $S_0=R_0$.

3. Inductive Hypothesis:

Assume that for some $k-1\ge 0$, the statement $S_{k-1}=R_{k-1}$ holds true. This means that all vertices at distance $k-1$ are precisely those with leave times in $[t_{k-1},t_k)$.

4. Inductive Step:

Let’s consider a vertex $v$ at distance $k$ ($v\in S_k$).

• $v$ enters the queue: $v$ is added to the queue only when its parent, $u$, is dequeued. Since $u$ is at distance $k-1$ ($u\in S_{k-1}$), by the inductive hypothesis, its leave time is in the interval $[t_{k-1},t_k)$.
• $v$’s leave time: Because BFS explores level by level, all vertices at distance $k-1$ must leave the queue before any vertex at distance $k$ is dequeued. Therefore, leave[v] must be greater than or equal to $t_k$.
• Upper bound on leave[v]: Since $t_{k+1}$ marks the start of processing level $k+1$, all vertices at level $k$ must leave the queue before this time. Therefore, leave[v] must be strictly less than $t_{k+1}$.
• Conclusion: Therefore, if $v\in S_k$, then $t_k\le \text{leave}[v]<t_{k+1}$, implying $v\in R_k$.

Now, let’s consider a vertex $v$ such that $t_k\le \text{leave}[v]<t_{k+1}$ ($v\in R_k$). This means $v$ is dequeued during the processing of level $k$. Since BFS processes vertices level by level, the distance of $v$ from the source must be $k$. Therefore, $v\in S_k$.

5. Conclusion:

We have shown that if $v\in S_k$, then $v\in R_k$, and vice-versa. Therefore, $S_k=R_k$ for all $k$, completing the proof by induction.

Cheapest Walks in Weighted Graphs

In weighted graphs, each edge is assigned a cost or weight. The cost of a walk is the sum of the weights of its constituent edges. The goal is often to find the cheapest or shortest path between two vertices, which corresponds to the walk with the minimum total cost.

Intro to Shortest Paths Problem (MIT)

I suggest you watch this good introduction to get intuition behind what’s going on…

Definitions and Notations

• Weighted Graph: $G=(V,E,c)$, where $V$ is the set of vertices, $E$ is the set of edges, and $c:E\to \mathbb{R}$ is a cost function assigning a real-valued weight to each edge.
• Cost of a Walk: Given a walk $W=(v_0,v_1,...,v_l)$, its cost is defined as: $c(W)={\sum }_{i=0}^{l-1}c(v_i,v_{i+1})$
• Cheapest Path (Shortest Path): The path between vertices $u$ and $v$ with the minimum cost is denoted as the cheapest path or shortest path.

• Distance: The cost of the cheapest path between vertices $u$ and $v$ is denoted as the distance $d(u,v)$. Formally: $d(u,v)=\min \{c(W)|W\text{ is a walk from }u\text{ to }v\}$

Negative Costs and Cycles

Allowing negative edge costs introduces the possibility of negative cycles – cycles whose total weight is negative. If a negative cycle is reachable from the source vertex, the shortest path problem becomes ill-defined, as traversing the cycle repeatedly would lead to arbitrarily low path costs ($d(u,v)\to -\infty$). Therefore, algorithms for finding shortest paths often assume the absence of negative cycles or explicitly detect them. More on this later…

Notation and Conventions

• Edge Notation: An edge from vertex $u$ to vertex $v$ is denoted as $(u,v)\in E$ or as $(u\to v)\in E$.
• Path Notation: A path is a sequence of vertices $(v_0,v_1,...,v_l)$ such that $(v_i\to v_{i+1})\in E$ for all $0\le i<l$.
• Walk Notation: Similar to a path but may contain repeated vertices or edges.

Structure of Cheapest Paths

A key property of cheapest paths in weighted graphs (without negative cycles) is the optimal substructure property. This means that any subpath of a cheapest path is itself a cheapest path between its endpoints. This property is crucial for the design of dynamic programming algorithms like Dijkstra’s algorithm and the Bellman-Ford algorithm.

Example

Consider this graph:

• If $x\ge 2$, the cheapest path from A to C has a cost of 6 (directly from A to C).
• If $-13\le x<2$, the cheapest path from A to C has a cost of $4+x$ (A to B to C).
• If $x<-13$, the cycle A-B-C-A becomes negative, making the shortest path to C from A undefined as it can be arbitrarily small.

This example illustrates how negative edge weights can lead to undefined shortest paths in the presence of negative cycles.

Cheapest Walks in Weighted Graphs

When dealing with weighted graphs, where edges have associated costs (weights), the goal often shifts from finding the shortest path (in terms of number of edges) to finding the cheapest path (minimum total weight). The presence of negative edge weights introduces complexities not present in unweighted graphs or graphs with non-negative weights.

Negative Weights and the Absence of Negative Cycles

Allowing negative edge weights opens the possibility of negative cycles. A negative cycle is a cycle where the sum of the weights of its edges is negative. The existence of a negative cycle fundamentally changes the problem:

• Infinitely Cheap Walks: If a negative cycle exists, it’s possible to construct arbitrarily cheap walks by repeatedly traversing the cycle. There is no minimum cost path or walk.
• No Shortest Path: The concept of a “shortest” or “cheapest” path becomes meaningless because any path can be made cheaper by adding more traversals of a negative cycle.

Therefore, to ensure the existence of a cheapest path, we must assume that no negative cycles exist in the graph. This assumption guarantees that any walk can be shortened to a path without increasing its cost. Any walk containing a cycle can have that cycle removed, leading to a path with the same or lower cost.

Triangle Inequality

The triangle inequality is a fundamental property of shortest paths (and cheapest walks in the absence of negative cycles) in a weighted graph.

Visually:

For any three vertices $u$, $v$, and $w$, the following inequality must hold:

$d(u,v)\le d(u,w)+d(w,v)$

where $d(x,y)$ represents the cost of the cheapest path (or walk) between vertices $x$ and $y$.

Intuitively, the triangle inequality asserts that the direct path from $u$ to $v$ cannot be more expensive than going through an intermediary vertex $w$. If it were, then the path through $w$ would not be optimal, violating the definition of $d(u,v)$. This property is crucial for many shortest-path algorithms.

Structure of Cheapest Paths: Subpath Optimality

A crucial property of cheapest paths in graphs without negative cycles is the principle of subpath optimality. This states that if a path $P$ from vertex $v_1$ to vertex $v_l$ is a cheapest path ($v_1\to v_2\to \cdots \to v_{l-1}\to v_l$), then any subpath of $P$ is also a cheapest path between its endpoints.

More formally: Let $P=(v_1,v_2,\dots ,v_l)$ be a cheapest path from $v_1$ to $v_l$. Then, for any $1\le i\le j\le l$, the subpath $(v_i,v_{i+1},\dots ,v_j)$ is a cheapest path from $v_i$ to $v_j$.

Proof:

We’ll prove this by contradiction. Suppose that the subpath $(v_i,v_{i+1},\dots ,v_j)$ is not a cheapest path from $v_i$ to $v_j$. This means there exists a shorter path $P^{\prime }$ from $v_i$ to $v_j$ with a lower cost. We can then construct a new path from $v_1$ to $v_l$ as follows:

1. Take the portion of $P$ from $v_1$ to $v_{i-1}$.
2. Append the path $P^{\prime }$.
3. Append the portion of $P$ from $v_{j+1}$ to $v_l$.

This new path has a lower cost than $P$ because we replaced a more expensive subpath with a cheaper one ($P^{\prime }$). This contradicts our initial assumption that $P$ was a cheapest path from $v_1$ to $v_l$. Therefore, the subpath $(v_i,v_{i+1},\dots ,v_j)$ must also be a cheapest path from $v_i$ to $v_j$.

The Importance of No Negative Cycles: This property crucially relies on the absence of negative cycles. If negative cycles existed, we could create cheaper paths by introducing cycles, invalidating the subpath optimality principle. The proof relies on the fact that replacing a subpath with a shorter one directly leads to a shorter overall path. This wouldn’t hold if negative cycles allowed us to make the entire path arbitrarily cheap by adding negative-cost cycles within it.

Cheapest Paths: Recurrence Relation and Dynamic Programming

We can formulate the problem of finding cheapest paths using a recurrence relation. Let $d(u,v)$ represent the cost of the cheapest path from vertex $u$ to vertex $v$. We can express $d(u,v)$ recursively as:

Where:

• $E$ is the set of edges in the graph.
• $c(u,w)$ is the cost (weight) of the edge from $u$ to $w$.
• The minimum is taken over all outgoing edges from $u$. If there are no outgoing edges from $u$ to any other vertices, then no paths exist to any other vertices from $u$, and the cost is $\infty$.

This recurrence says that the cheapest path from $u$ to $v$ is either 0 if $u$ and $v$ are the same vertex, or the minimum cost among all paths that go from $u$ to some neighbor $w$ and then continue to $v$ from there using the cheapest path from $w$ to $v$.

Dynamic Programming Approach

This recurrence relation naturally lends itself to a dynamic programming (DP) solution. We can compute the values of $d(u,v)$ iteratively using a table (or matrix) to store the results. A naive recursive implementation of the recurrence relation, while conceptually straightforward, is highly inefficient. It suffers from redundant calculations and, in the presence of cycles, can lead to infinite recursion. Therefore, a DP approach is essential. We avoid memoization (top-down DP) in favor of a bottom-up DP strategy because of the risk of infinite recursion due to cycles. A smart calculation order is required to guarantee that we compute all the necessary distances before they’re needed.

Calculation Order

The choice of calculation order is crucial to ensure that when computing the shortest distance from $u$ to $v$, all necessary $d(w,v)$ values (shortest distances from neighbors $w$ of $u$ to $v$) have already been computed. This avoids the pitfalls of recursion and ensures that we get the optimal solution. Several approaches can efficiently determine this order:

• Iterative Approach (Bellman-Ford): This approach iteratively relaxes all edges in the graph. In each iteration, the algorithm processes all edges and updates the distances if a shorter path is found. This process repeats for $|V|-1$ iterations, where $|V|$ is the number of vertices. After this the algorithm checks for negative cycles. If no negative cycles exist, the algorithm will have correctly computed the shortest paths to all vertices reachable from the source. If negative cycles exist, this will be detected in this final checking step. The key is that each iteration ensures all distances from a vertex to each of its reachable vertices are calculated before moving to the next iteration.

• Topological Sort (for Directed Acyclic Graphs): For directed acyclic graphs (DAGs), topological sorting provides a highly efficient calculation order. A topological sort orders vertices such that for every directed edge $(u,v)$, vertex $u$ precedes vertex $v$ in the ordering. Processing vertices in this order guarantees that when we compute $d(u,v)$, the distances $d(w,v)$ for all neighbors $w$ of $u$ have already been computed. This is because the topological order ensures we process all predecessors before their successors. There are no cycles to cause computational problems or issues with dependencies.

The choice between Bellman-Ford and the topological sort approach depends on the graph structure. Bellman-Ford is more general and handles graphs with cycles (provided no negative cycles exist), while topological sorting is more efficient for DAGs (Directed Acyclic Graphs). The use of either of these methods replaces the inefficient top-down recursive solution based directly on the recurrence relation with an efficient iterative approach that avoids recursive loops by imposing a well-defined computation order.

DAG shortest path and Dijkstra's Algorithm (MIT)

Once again, I suggest watching this video to get a better understanding…

Acyclical Graphs and Topological Sorting

In directed acyclic graphs (DAGs), the absence of cycles simplifies the computation of cheapest paths significantly. Topological sorting provides an optimal ordering for the dynamic programming approach.

Topological Sorting: A topological sort of a DAG is a linear ordering of all its vertices such that for every directed edge $(u,v)$ from vertex $u$ to vertex $v$, vertex $u$ comes before vertex $v$ in the ordering.

Algorithm:

1. Topological Sort: Obtain a topological ordering of the vertices (various algorithms exist for this, often using depth-first search).
2. Initialization: Initialize the distance array d[] as follows: d[source] = 0, d[v] = ∞ for all other vertices v.
3. Iteration: Iterate through the vertices in topological order. For each vertex u, consider its outgoing edges $(u,v)$. If d[u] + c(u, v) < d[v], update d[v] to d[u] + c(u, v).

Runtime: Topological sorting takes $\mathcal{O}(|V|+|E|)$ time. The subsequent iterative step also takes $\mathcal{O}(|V|+|E|)$ time. Thus, the overall algorithm has a linear time complexity. This is a significant improvement over algorithms that work on general graphs (like Bellman-Ford), which can have a runtime of $\mathcal{O}(|V|\times |E|)$.

Cheapest Paths in Graphs with Non-Negative Edge Costs

Finding the cheapest paths in graphs with non-negative edge costs is a fundamental graph problem with numerous applications. The absence of negative edge weights simplifies the problem significantly, allowing for efficient algorithms like Dijkstra’s algorithm. However, understanding the underlying principles is important for appreciating the algorithm’s efficiency and correctness.

Assumptions and Definitions

1. Non-negative Edge Costs: We assume that the cost (weight) of every edge in the graph is non-negative. This is crucial for the correctness and efficiency of the algorithms discussed here.

2. Weighted Graph: The graph $G=(V,E)$ is a weighted directed graph, where $V$ is the set of vertices and $E$ is the set of directed edges. Each edge $(u,v)\in E$ has a non-negative weight $c(u,v)\ge 0$.

3. Cheapest Path: For any pair of vertices $u,v\in V$, we denote the cost of the cheapest path from $u$ to $v$ as $d(u,v)$. If no path exists from $u$ to $v$, then $d(u,v)=\infty$.

Recurrence Relation

The cost of the cheapest path from vertex $u$ to vertex $v$, denoted as $d(u,v)$, can be expressed recursively:

This recurrence relation states that the cheapest path from $u$ to $v$:

• Is 0 if $u$ and $v$ are the same vertex.
• Otherwise, it’s the minimum cost among all paths that go from $u$ to a neighbor $w$ (via an edge $(u,w)$), and then continue from $w$ to $v$ along a cheapest path. The cost of such a path is the edge cost $c(u,w)$ plus the cost of the cheapest path from $w$ to $v$, which is $d(w,v)$.

Important Note on Calculation Order and Implicit Sorting

To avoid infinite recursion and ensure efficient computation, we need to carefully consider the order in which we compute $d(u,v)$ values. Algorithms like Dijkstra’s implicitly sort vertices based on their distances from the source. We can think of this as iteratively considering vertices in increasing order of distance from the source.

Let’s assume we have already computed the shortest distances to vertices $v_1,v_2,...,v_{k-1}$ from the source and that we have $d(source,v_i)$ for $i<k$. When computing $d(u,v)$ for a given vertex $v$, we compute:

Why the condition $i<k$? The condition $i<k$ ensures that when calculating $d(u,v)$, we only consider paths that go through vertices whose shortest distances from the source have already been computed. This is crucial because the recurrence relation relies on having already calculated the shortest distances to the predecessors before we can compute the shortest distance to the current vertex.

If we didn’t have this condition, the algorithm could potentially consider paths that are not yet optimal, leading to incorrect results. The implicit sorting ensures that this condition is always met, leading to a correct and efficient calculation of shortest distances.

Proof of Correctness (for Non-Negative Edge Costs)

We want to prove that for any vertex $v_k$, the cheapest path from the source $s$ to $v_k$ is correctly computed by the recurrence: $d(s,v_k)={\min }_{(v_i,v_k)\in E,i<k}\{d(s,v_i)+c(v_i,v_k)\}$. We’ll assume vertices are considered in non-decreasing order of their distances from the source.

1. Subpath Optimality: As before, this proof relies on the subpath optimality property, which holds for graphs with non-negative edge costs.

2. Contradiction Setup: Assume, for the sake of contradiction, that there exists a vertex $v_k$ for which the recurrence calculates an incorrect shortest path cost. This means there is a cheaper path to $v_k$ than the one found by the recurrence.

3. The Contradiction: Let’s assume that the last edge of the actual cheapest path to $v_k$ is from some vertex $v_i$ to $v_k$ with $i>k$. This means we are considering a vertex ($v_i$) that comes after $v_k$ in the order of non-decreasing distance from the source. Since the costs are non-negative we have:

$d(s,v_i)\ge d(s,v_k)$ (because $i>k$ and we process vertices in order of increasing distance from $s$)

$d(s,v_i)+c(v_i,v_k)\underset{\text{Non-negative costs}}{\underbrace{\ge }}d(s,v_k)$

If $d(s,v_i)+c(v_i,v_k)>d(s,v_k)$ this contradicts the assumption of the cheapest path using $v_i$ as a predecessor since there would exist a better path using the shortest path from $s$ to $v_k$ calculated earlier. This implies $d(s,v_i)+c(v_i,v_k)=d(s,v_k)$. If $v_k$ can be reached via a shorter path at all, this shortest path cannot traverse a vertex processed later. If a shorter path uses only vertices processed earlier, this path would be found by the recurrence relation.

Therefore, our initial assumption of an incorrect shortest path cost calculated by the recurrence must be false. This concludes the proof by contradiction.

A Useful Recurrence Relation and Algorithm for Cheapest Paths

The recurrence relation for computing cheapest paths, $d(u,v)={\min }_{(u,w)\in E}\{c(u,w)+d(w,v)\}$, initially seems circular: it requires knowing the shortest distances to compute the shortest distance, creating a dependency issue. However, this circularity can be resolved by carefully orchestrating the order of computation. The key is to compute the shortest distances and their associated ordering simultaneously.

Core Idea: The algorithm iteratively builds a set $S$ of vertices for which we’ve definitively determined the cheapest paths from the source vertex $s$. Crucially, vertices are added to $S$ in non-decreasing order of their shortest path distances from $s$. This ordering is what breaks the circular dependency in the recurrence relation.

Recurrence Relation and Notation

Let $d_S(v)$ denote the shortest distance from the source $s$ to vertex $v$ considering only paths that use vertices from the set $S\cup \{v\}$. This allows us to define a non-circular recurrence:

This recurrence states:

• The distance from $s$ to $s$ is 0.
• If $v$ is already in $S$, its shortest distance is already known.
• If $v$ is not in $S$, we consider all incoming edges from vertices in $S$ and choose the path with the minimum cost. This path is composed of the shortest path from $s$ to some vertex $u$ in $S$, followed by the edge from $u$ to $v$.
• If there’s no path from $s$ to $v$, the distance is infinity.

The Algorithm’s Strategy: The algorithm repeatedly selects the vertex $v^{\ast }$ with the minimum $d_S(v^{\ast })$ value from among the vertices not yet in $S$. The key is that, because the algorithm expands this set in this manner, by the time it examines a vertex, the shortest distances to all its predecessors will be already computed, making the recurrence non-circular and allowing the algorithm to correctly compute $d(s,v^{\ast })$. Then $v^{\ast }$ is added to $S$, and the distances to its neighbors are updated based on the recurrence, iteratively solving the problem efficiently.

Proof of Correctness

The algorithm maintains a set $S$ of vertices whose shortest distances from the source $s$ have been definitively determined. The algorithm iteratively adds vertices to $S$ by selecting the vertex $v^{\ast }\notin S$ with the smallest tentative distance $d_S(v^{\ast })$, where:

$d_S(v^{\ast })={\min }_{u\in S}\{d(s,u)+c(u,v^{\ast })\}$

Here, $d(s,u)$ is the known shortest distance from $s$ to $u$ (since $u\in S$), and $c(u,v^{\ast })$ is the cost of the direct edge from $u$ to $v^{\ast }$.

Claim: When the algorithm selects $v^{\ast }$, its tentative distance $d_S(v^{\ast })$ is equal to the true shortest path distance $d(s,v^{\ast })$.

Proof by Contradiction:

1. Assumption: Assume, for contradiction, that $d(s,v^{\ast })\ne d_S(v^{\ast })$. This implies that there is a cheaper path from $s$ to $v^{\ast }$ than the one found by $d_S(v^{\ast })$.

2. Alternative Path: Let $W$ be such a cheaper path from $s$ to $v^{\ast }$. Since $v^{\ast }\notin S$, this path $W$ must leave the set $S$ at some point. Let $u$ be the last vertex in $S$ along the path $W$, and let $v$ be the first vertex outside $S$ along $W$. (Note that $v$ might be $v^{\ast }$ itself).

3. Cost Analysis: The cost of the path $W$ can be expressed as:

   $c(W)=d(s,u)+c(u,v)+d(v,v^{\ast })$

   where:

   • $d(s,u)$ is the known shortest path cost from $s$ to $u$ (since $u\in S$).
   • $c(u,v)$ is the cost of the edge $(u,v)$.
   • $d(v,v^{\ast })$ is the cost of the subpath from $v$ to $v^{\ast }$.

4. Non-negative Edge Costs: Since all edge costs are non-negative, $d(v,v^{\ast })\ge 0$. Therefore:

   $c(W)\ge d(s,u)+c(u,v)$

5. The Contradiction: We know that $d_S(v)$ is the minimal path going from any node in S to $v$, therefore $d(s,u)+c(u,v)\ge d_S(v)$. Because of the non-negative edge costs, we know that the cost of going from $s\to v^{\ast }$ must at least be $d_S(v)$ therefore $d_S(v^{\ast })\le d_S(v)$. Since we chose $v^{\ast }$ such that $d_S(v^{\ast })$ is minimal we have $d_S(v^{\ast })\le d_S(v)\le c(W)$. This contradicts our assumption that $W$ is a cheaper path than the one implied by $d_S(v^{\ast })$.

Therefore, our initial assumption must be false, and we conclude that $d(s,v^{\ast })=d_S(v^{\ast })$ when $v^{\ast }$ is selected by the algorithm.

Note for readers: For a less confusing explanation, watch this video…

Dijkstra’s Algorithm

Dijkstra’s algorithm is a greedy algorithm that efficiently computes the shortest paths from a single source vertex to all other vertices in a weighted graph with non-negative edge costs. Its efficiency stems from a clever strategy of iteratively selecting vertices in increasing order of their shortest distance estimates from the source.

Algorithm Explanation

1. Initialization:

   • Set the distance to the source vertex to 0 ($d(s,s)=0$).
   • Set the distance to all other vertices to infinity ($d(s,v)=\infty$ for all $v\ne s$).
   • Create a set $S$ initially containing only the source vertex $s$ ($S=\{s\}$). $S$ tracks vertices whose shortest distances from the source have been definitively determined.
   • Create a priority queue $Q$ containing all vertices, prioritized by their tentative distances.

2. Iteration: While the priority queue $Q$ is not empty:

   • Select the vertex $u$ with the smallest tentative distance from the priority queue $Q$.
   • Add $u$ to the set $S$.
   • For each neighbor $v$ of $u$ such that $v\notin S$:
   • Relax the edge $(u,v)$: If $d(s,u)+c(u,v)<d(s,v)$, update $d(s,v)$ to $d(s,u)+c(u,v)$ and update the priority queue accordingly.

3. Termination: Once the priority queue is empty, the algorithm terminates, and $d(s,v)$ represents the shortest distance from the source $s$ to each vertex $v$.

Pseudocode

Alternatively:

def dijkstra(graph, start):
    # Initialize distances: all nodes are at "infinity" except the start node (0 distance to itself)
    distances = {node: infinity for each node in graph}
    distances[start] = 0
    
    # Create a priority queue to process nodes in the order of their distance from the start
    priority_queue = [(0, start)]  # (distance, node)
 
    while priority_queue is not empty:
        # Get the node with the smallest distance from the queue
        current_distance, current_node = pop the smallest item from priority_queue
        
        # For each neighboring node:
        for neighbor, weight in graph[current_node]:
            # Calculate the total distance to the neighbor
            distance = current_distance + weight
            
            # If this new distance is shorter than the previously known distance:
            if distance < distances[neighbor]:
                # Update the distance to this neighbor
                distances[neighbor] = distance
                
                # Add the neighbor to the queue for further exploration
                push (distance, neighbor) into priority_queue
 
    return distances
 

Runtime Analysis

The runtime of Dijkstra’s algorithm depends heavily on the implementation of the priority queue.

• Using a binary heap: The priority queue operations (insertion, deletion, and finding the minimum) take $\mathcal{O}(\log |V|)$ time in a binary heap. Since each vertex is added to and removed from the priority queue at most once, and each edge is processed at most once, the overall runtime is $\mathcal{O}((|V|+|E|)\log |V|)$, where $|V|$ is the number of vertices and $|E|$ is the number of edges.

• Using a Fibonacci heap: Fibonacci heaps offer amortized $\mathcal{O}(1)$ time for decrease-key operations. This leads to an improved runtime of $\mathcal{O}(|E|+|V|\log |V|)$. However, Fibonacci heaps are more complex to implement.

In practice, the binary heap implementation is often preferred due to its simplicity and reasonable performance, especially for graphs that are not excessively large. The use of a priority queue is key to achieving the efficient $\mathcal{O}((|V|+|E|)\log |V|)$ runtime. Without it, the runtime would be significantly worse.

Continue here: 12 Cheapest Path Problem, Negative Cost, Bellman-Ford, Minimum Spanning Trees, Boruvka’s Algorithm, Prim’s Algorithm, Priority Queues