## Lecture 14. Shortest Paths - Part 1
- Bellman-Ford
- Dijkstra
---
### Shortest Paths Problem
- Single-Source Shortest Paths (SSSP)
- All-Pairs Shortest Paths (APSP)
---
#### Weighted graph
- A **weighted graph** is a graph that has a numeric (for example, integer) label $w(e)$ associated with each edge $e$, called the **weight** of edge $e$.
- For $e = (u,v)$, we let notation $w(u,v) = w(e)$.
---
#### Weighted graph
- Let $G$ be a weighted graph. The **length** (or **weight**) of a **path $P$** is the sum of the weights of the edges of $P$.
- The **distance** from a vertex $u$ to a vertex $v$ in $G$, denoted $d(u,v)$, is the length of a minimum-length path (also called **shortest path**) from $u$ to $v$, if such a path exists.
---
#### Weighted graph: Major US Airports
<img src="https://cdn.ucode.vn/uploads/1/upload/xDbcksFZ.png" class="element-left content-img" />
---
#### Shortest Paths: SSSP
- Single-Source Shortest Paths(SSSP): Given a **weighted** graph G and a source vertex $s$, what are the shortest paths from $s$ to all other vertices of $G$?
---
#### Shortest Paths: SSSP
- Single-Source Shortest Paths(SSSP): Given a **weighted** graph G and a source vertex $s$, what are the shortest paths from $s$ to all other vertices of $G$?
- For **unweighted** graph?
---
#### Shortest Paths: SSSP
- For **unweighted** graph: BFS with compexity of $O(E+V)$
---
#### Shortest Paths: SSSP
For **weighted** graph G:
- The shortest path between two vertices $u$ and $v$ in a graph $G$ that has no negative and no zero-weight weight cycle must be a simple path (**acyclic**).
- Subpaths of shortest paths from $u$ to $v$ are shortest paths!
---
#### Shortest Paths: SSSP
- If there is a cycle in $G$ whose total weight is negative (**negative cycles**), the **distance** from $u$ to $v$ may not be defined.
- Graphs with Non-negative Weights: **Dijkstra** algorithm
- Graphs with Arbitrary Weights (without **negative cycles**): **Bellman–Ford** algorithm
---
### Bellman–Ford algorithm
---
#### Bellman–Ford algorithm
- The Bellman–Ford algorithm finds shortest paths from **a starting node** to all nodes of the graph.
- The algorithm can process **all kinds of graphs**, provided that the graph does **not contain a cycle with negative length**.
- If the graph contains a negative cycle, the algorithm can detect this.
---
#### Bellman–Ford algorithm
- The algorithm keeps track of distances from the starting node to all nodes of the graph.
- Initially, the distance to the starting node is $0$ and the distance to all other nodes in **infinite**.
- The algorithm **reduces** the distances by finding edges that **shorten** the paths until it is not possible to reduce any distance.
---
#### Bellman–Ford algorithm
- Initially, the distance to the starting node is $0$, and the distance to all other nodes is **infinite**.
<img src="https://cdn.ucode.vn/uploads/1/upload/aAkUstDO.png" class="element-left content-img" />
---
#### Bellman–Ford algorithm
- The algorithm searches for edges that reduce distances. First, all edges from node $1$ reduce distances:
<img src="https://cdn.ucode.vn/uploads/1/upload/OHiTTHWH.png" class="element-left content-img" />
---
#### Bellman–Ford algorithm
- After this, edges $2 \rightarrow 5$ and $3 \rightarrow 4$ reduce distances:
<img src="https://cdn.ucode.vn/uploads/1/upload/tcSKwdHk.png" class="element-left content-img" />
---
#### Bellman–Ford algorithm
- Finally, there is one more change:
<img src="https://cdn.ucode.vn/uploads/1/upload/BXOATjzb.png" class="element-left content-img" />
---
#### Bellman–Ford algorithm
- After this, no edge can reduce any distance: the distances are **final**:
<img src="https://cdn.ucode.vn/uploads/1/upload/BXOATjzb.png" class="element-left content-img" />
---
#### Bellman–Ford algorithm: implementation
```python=
class Graph:
def __init__(self, vertices):
self.V = vertices # Total number of vertices in the graph
self.graph = [] # Array of edges: [(u, v, w)]
def add_edge(self, s, d, w):
self.graph.append([s, d, w])
def print_solution(self, dist):
print("Vertex Distance from Source")
for i in range(self.V):
print("{0}\t\t{1}".format(i, dist[i]))
def bellman_ford(self, src):
dist = [float("Inf")] * self.V
dist[src] = 0
# relax edges |V| - 1 times
for _ in range(self.V - 1):
for s, d, w in self.graph:
dist[d] = min(dist[d], dist[s] + w)
# detect negative cycle
for s, d, w in self.graph:
if dist[s] + w < dist[d]:
print("Graph contains negative weight cycle")
return
# No negative weight cycle found!
self.print_solution(dist)
```
Note:
```python
class Graph:
def __init__(self, vertices):
self.V = vertices # Total number of vertices in the graph
self.graph = [] # Array of edges
# Add edges
def add_edge(self, s, d, w):
self.graph.append([s, d, w])
# Print the solution
def print_solution(self, dist):
print("Vertex Distance from Source")
for i in range(self.V):
print("{0}\t\t{1}".format(i, dist[i]))
def bellman_ford(self, src):
# Step 1: fill the distance array and predecessor array
dist = [float("Inf")] * self.V
# Mark the source vertex
dist[src] = 0
# Step 2: relax edges |V| - 1 times
for _ in range(self.V - 1):
for s, d, w in self.graph:
if dist[s] != float("Inf") and dist[s] + w < dist[d]:
dist[d] = dist[s] + w
# Step 3: detect negative cycle
# if value changes then we have a negative cycle in the graph
# and we cannot find the shortest distances
for s, d, w in self.graph:
if dist[s] != float("Inf") and dist[s] + w < dist[d]:
print("Graph contains negative weight cycle")
return
# No negative weight cycle found!
# Print the distance and predecessor array
self.print_solution(dist)
g = Graph(5)
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 4)
g.add_edge(1, 3, 3)
g.add_edge(2, 1, 6)
g.add_edge(3, 2, 2)
g.bellman_ford(0)
```
---
#### Bellman–Ford algorithm: complexity
```python=
g = Graph(5)
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 4)
g.add_edge(1, 3, 3)
g.add_edge(2, 1, 6)
g.add_edge(3, 2, 2)
g.bellman_ford(0)
# 0 0
# 1 5
# 2 4
# 3 8
# 4 inf
```
---
#### Bellman–Ford algorithm: complexity
- The time complexity of the algorithm is $O(|V| * |E|)$, ($|V| − 1$ rounds and iterates through all $|E|$ edges during a round).
- If there are no negative cycles in the graph, all distances are final after $|V| − 1$ rounds, because each shortest path can contain at most $|V| − 1$ edges.
- More efficient: stop the algorithm if no distance can be reduced during a round.
---
#### Negative cycles
- A negative cycle can be detected using the Bellman–Ford algorithm by running the algorithm for $|V|$ rounds. If the last round reduces any distance, the graph contains a negative cycle.
<img src="https://cdn.ucode.vn/uploads/1/upload/bdsTjLyP.png" class="element-left content-img" />
---
### Dijkstra’s algorithm
---
#### Dijkstra’s algorithm
- Finds shortest paths from the starting node to all nodes of the graph, like the Bellman–Ford algorithm.
- More efficient and can be used for processing large graphs.
- Requires that there are **no negative weight edges** in the graph
---
#### Dijkstra’s algorithm
- Like the Bellman–Ford algorithm, Dijkstra’s algorithm maintains distances to the nodes and reduces them during the search.
- Dijkstra’s algorithm is efficient, because it only processes **each edge in the graph once**, using the fact that there are no negative edges.
---
#### Dijkstra’s algorithm
- The starting node is node 1, initially the distance to the starting node is $0$ and the distance to all other nodes is **infinite**.
<img src="https://cdn.ucode.vn/uploads/1/upload/RCunPZDm.png" class="element-left content-img" />
---
#### Dijkstra’s algorithm
- At each step, Dijkstra’s algorithm selects a node that has **not been processed** yet and whose **distance is as small as possible**. The first such node is node $1$ with distance $0$.
<img src="https://cdn.ucode.vn/uploads/1/upload/BCnQJsho.png" class="element-left content-img" />
---
#### Dijkstra’s algorithm
- The next node to be processed is node $5$ with distance $1$. This reduces the distance to node $4$ from $9$ to $3$:
<img src="https://cdn.ucode.vn/uploads/1/upload/acUoHxmG.png" class="element-left content-img" />
---
#### Dijkstra’s algorithm
- After this, the next node is node $4$, which reduces the distance to node $3$ to $9$:
<img src="https://cdn.ucode.vn/uploads/1/upload/PyivLyVb.png" class="element-left content-img" />
---
#### Dijkstra’s algorithm
- A remarkable property: **whenever a node is selected, its distance is final**.
- At this point: the distances $0$, $1$ and $3$ are the final distances to nodes $1$, $5$ and $4$.
<img src="https://cdn.ucode.vn/uploads/1/upload/PyivLyVb.png" class="element-left content-img" />
---
#### Dijkstra’s algorithm
- After this, the algorithm processes the two remaining nodes, and the final distances are as follows:
<img src="https://cdn.ucode.vn/uploads/1/upload/PwtLDiIS.png" class="element-left content-img" />
---
#### Negative edges
- If there is a negative edge, the algorithm may give incorrect results. As an example, consider the following graph:
<img src="https://cdn.ucode.vn/uploads/1/upload/yVYmDDmx.png" class="element-left content-img" />
---
#### Negative edges
<img src="https://cdn.ucode.vn/uploads/1/upload/yVYmDDmx.png" class="element-left content-img" />
- The shortest path from node $1$ to node $4$ is $1 → 3 → 4$ and its length is $1$.
- However, Dijkstra’s algorithm finds the path $1 → 2 → 4$ by following the minimum weight edges.
Note:
- The algorithm does not take into account that on the other path, the weight −5 compensates the previous large weight 6.
---
#### Dijkstra’s algorithm: Adjacency Matrix
```python=
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0] * self.V for row in range(self.V)]
def print_solution(self, dist):
print("Vertex \t Distance from Source")
for node in range(self.V):
print(node, "\t\t", dist[node])
# A utility function to find the vertex with minimum distance value,
# from the set of vertices not yet included in the shortest path tree
def min_distance(self, dist, visited):
dmin = float("inf")
# Search not nearest vertex not in the shortest path tree
for v in range(self.V):
if dist[v] < dmin and not visited[v]:
dmin = dist[v]
min_index = v
return min_index
# Dijkstra's algorithm for a graph represented using adjacency matrix representation
def dijkstra(self, src):
dist = [float("inf")] * self.V
dist[src] = 0
visited = [False] * self.V
for _ in range(self.V):
# Pick the minimum distance vertex from the set of vertices not yet processed.
# u is always equal to src in first iteration
u = self.min_distance(dist, visited)
# Put the minimum distance vertex in the shortest path tree
visited[u] = True
# Update dist value of the adjacent vertices of the picked vertex only if the current
# distance is greater than new distance and the vertex in not in the shortest path tree
for v in range(self.V):
if self.graph[u][v] > 0 and not visited[v] and dist[v] > dist[u] + self.graph[u][v]:
dist[v] = dist[u] + self.graph[u][v]
self.print_solution(dist)
```
---
#### Dijkstra’s algorithm: Adjacency Matrix
<img src="https://cdn.ucode.vn/uploads/1/upload/YIeIKqdF.png" class="element-left content-img" />
```python=
g = Graph(9)
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
]
g.dijkstra(0)
# 0 0
# 1 4
# 2 12
# 3 19
# 4 21
# 5 11
# 6 9
# 7 8
# 8 14
```
---
#### Dijkstra’s algorithm: Adjacency Matrix
- Step 1:
<img src="https://cdn.ucode.vn/uploads/1/upload/IXfeEnRA.png" class="element-left content-img" width="30%" />
---
#### Dijkstra’s algorithm: Adjacency Matrix
- Step 2:
<img src="https://cdn.ucode.vn/uploads/1/upload/KDDFejuJ.png" class="element-left content-img" width="50%" />
---
#### Dijkstra’s algorithm: Adjacency Matrix
- Step 3:
<img src="https://cdn.ucode.vn/uploads/1/upload/UzFoAQwf.png" class="element-left content-img" width="50%" />
---
#### Dijkstra’s algorithm: Adjacency Matrix
- Step 4:
<img src="https://cdn.ucode.vn/uploads/1/upload/rwfZmwft.png" class="element-left content-img" width="60%"/>
---
#### Dijkstra’s algorithm: Adjacency Matrix
- Final:
<img src="https://cdn.ucode.vn/uploads/1/upload/AVPBjpaw.png" class="element-left content-img" width="80%"/>
---
#### Dijkstra's Algorithm Complexity
- Adjacency Matrix
- $O(|V|^2)$
---
#### Dijkstra’s algorithm: Adjacency List using Heap
```python=
import heapq
class Graph:
def __init__(self, V: int): # Constructor
self.V = V
self.adj = [[] for _ in range(V)] # adjacency list
def add_edge(self, u: int, v: int, w: int):
self.adj[u].append((v, w))
self.adj[v].append((u, w))
# Prints shortest paths from src to all other vertices
def shortest_path(self, src: int):
# Create a priority queue to store vertices that are being preprocessed
pq = []
heapq.heappush(pq, (0, src))
# Create a vector for distances and initialize all distances as infinite (INF)
dist = [float('inf')] * self.V
dist[src] = 0
while pq:
# The first vertex in pair is the minimum distance vertex, extract it from priority queue.
# vertex label is stored in second of pair
d, u = heapq.heappop(pq)
# 'i' is used to get all adjacent vertices of a vertex
for v, weight in self.adj[u]:
# If there is shorted path to v through u.
if dist[v] > dist[u] + weight:
# Updating distance of v
dist[v] = dist[u] + weight
heapq.heappush(pq, (dist[v], v))
# Print shortest distances stored in dist[]
for i in range(self.V):
print(f"{i} \t\t {dist[i]}")
```
---
#### Dijkstra’s algorithm: using Heap
<img src="https://cdn.ucode.vn/uploads/1/upload/YIeIKqdF.png" class="element-left content-img" />
```python=
V = 9
g = Graph(V)
g.addEdge(0, 1, 4)
g.addEdge(0, 7, 8)
g.addEdge(1, 2, 8)
g.addEdge(1, 7, 11)
g.addEdge(2, 3, 7)
g.addEdge(2, 8, 2)
g.addEdge(2, 5, 4)
g.addEdge(3, 4, 9)
g.addEdge(3, 5, 14)
g.addEdge(4, 5, 10)
g.addEdge(5, 6, 2)
g.addEdge(6, 7, 1)
g.addEdge(6, 8, 6)
g.addEdge(7, 8, 7)
g.shortestPath(0)
# 0 0
# 1 4
# 2 12
# 3 19
# 4 21
# 5 11
# 6 9
# 7 8
# 8 14
```
---
#### Dijkstra's Algorithm Complexity
- Adjacency List
- Using Heap (Priority Queue)
- $O(|E| \times log(|V|))$
---
## The End
{"metaMigratedAt":"2023-06-17T19:46:15.427Z","metaMigratedFrom":"YAML","breaks":true,"description":"View the slide with \"Slide Mode\".","slideOptions":"{\"theme\":\"white\"}","title":"Thuc Nguyen's ADSA Course - Lecture 14. Shortest Paths - P1","contributors":"[{\"id\":\"476f9158-9a39-4a2d-bb09-ce08dd7eb978\",\"add\":22811,\"del\":6773}]"}