## Lecture 15. Shortest Paths - Part 2
- Single-Source Path
- All-Shortest Pairs Shortest Path (Floyd-Warshall)
---
### Floyd–Warshall algorithm
- Finds **all shortest paths** between the nodes in a single run
- Maintains a two-dimensional array that contains distances between the nodes.
- Named after R. W. Floyd and S. Warshall who published it independently in 1962
---
### Floyd–Warshall algorithm
- Maintains a two-dimensional array that contains distances between the nodes.
- First, distances are calculated only using direct edges between the nodes.
- After this, the algorithm reduces distances by using intermediate nodes in paths.
---
### Floyd–Warshall algorithm
Initially:
<br/>
<img src="https://cdn.ucode.vn/uploads/1/upload/SIhASJmr.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/lvSLpacW.png" class="element-left content-img" />
---
### Floyd–Warshall algorithm
- The algorithm consists of consecutive rounds.
- On each round, the algorithm selects a new node that can act as an intermediate node in paths, and reduces the distances using this node.
---
### Floyd–Warshall algorithm
- On the first round, node $1$ is the new intermediate node.
<img src="https://cdn.ucode.vn/uploads/1/upload/SIhASJmr.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/eyXeiqds.png" class="element-left content-img" />
---
### Floyd–Warshall algorithm
- On the second round, node $2$ is the new intermediate node.
<img src="https://cdn.ucode.vn/uploads/1/upload/SIhASJmr.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/EPuzAthm.png" class="element-left content-img" />
---
### Floyd–Warshall algorithm
- On the third round, node $3$ is the new intermediate round.
<img src="https://cdn.ucode.vn/uploads/1/upload/SIhASJmr.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/FnMpyumX.png" class="element-left content-img" />
---
### Floyd–Warshall algorithm
- The algorithm continues like this, until all nodes have been appointed intermediate nodes.
<img src="https://cdn.ucode.vn/uploads/1/upload/SIhASJmr.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/wPUMUOvr.png" class="element-left content-img" />
---
### Floyd–Warshall algorithm
- For example, the array tells us that the shortest distance between nodes $2$ and $4$ is $8$.
<img src="https://cdn.ucode.vn/uploads/1/upload/VRVPNiMU.png" class="element-left content-img" />
<img src="https://cdn.ucode.vn/uploads/1/upload/wPUMUOvr.png" class="element-left content-img" />
---
### Floyd–Warshall algorithm
```python=
def floyd_warshall(graph):
dist = [row[:] for row in graph]
n = len(graph)
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
```
---
### Floyd–Warshall algorithm
```python=
INF = float("inf")
G = [[0, 3, INF, 5],
[2, 0, INF, 4],
[INF, 1, 0, INF],
[INF, INF, 2, 0]]
res = floyd_warshall(G)
for row in res:
print(*row)
# 0 3 7 5
# 2 0 6 4
# 3 1 0 5
# 5 3 2 0
```
---
### Floyd–Warshall algorithm
- Time complexity of the algorithm is $O(n^3)$ $\rightarrow$ small graphs
- The implementation is simple
---
## Shortest Paths
- Single-Source Shortest Paths (SSSP)
- Bellman-Ford:
- Graph without **negative cycles**
- $O(|E| \times |V|)$
- Dijkstra:
- Graph without **negative weights**
- $O(|E| \times log(|V|))$
- All-Pairs Shortest Paths (APSP)
- Floyd–Warshall
- $O(|V|^3)$
---
## Longest Path Problem
- Longest path problem is the problem of finding a simple path of **maximum length** in a given graph.
- **Unweighted longest path** problem: NP-complete
- Hamiltonian path problem: a graph $G$ has a Hamiltonian path if and only if its longest path has length $|V| − 1$: NP-complete
---
### Longest Path Problem
- The longest path problem in a **weighted graph** $G$ $\rightarrow$ shortest path in a graph $−G$ derived from $G$ by **negating** its weights.
- For most graphs, this transformation is not useful because it creates **negative cycles** in $−G$.
- For DAG (directed acyclic graph) $\rightarrow$ **topological ordering**
---
## The End
{"metaMigratedAt":"2023-06-17T19:46:15.991Z","metaMigratedFrom":"YAML","breaks":true,"description":"View the slide with \"Slide Mode\".","slideOptions":"{\"theme\":\"white\"}","title":"Thuc Nguyen's ADSA Course - Lecture 15. Shortest Paths - P2","contributors":"[{\"id\":\"476f9158-9a39-4a2d-bb09-ce08dd7eb978\",\"add\":4757,\"del\":20}]"}