Graph Bellman Ford¶
Table of Contents¶
- 743. Network Delay Time (Medium)
- 787. Cheapest Flights Within K Stops (Medium)
743. Network Delay Time¶
-
Tags: Depth First Search, Breadth First Search, Graph, Heap Priority Queue, Shortest Path
"""
- Return the minimum time taken to reach all nodes in a network.
- Shortest Path Problem: Find the shortest path between two vertices in a graph.
- Dijkstra's Algorithm
- Shortest path algorithm
- Weighted graph (non-negative weights)
- Data Structure: Heap; Hash Set
- Time Complexity: O(E * logV)
- Space Complexity: O(V)
"""
import heapq
from collections import defaultdict
from typing import List
# Dijkstra - Set
def networkDelayTime1(times: List[List[int]], n: int, k: int) -> int:
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
heap = [(0, k)]
visit = set()
t = 0
while heap:
w1, n1 = heapq.heappop(heap)
if n1 in visit:
continue
visit.add(n1)
t = w1
for n2, w2 in graph[n1]:
heapq.heappush(heap, (w1 + w2, n2))
return t if len(visit) == n else -1
# Dijkstra - Dict
def networkDelayTime2(times: List[List[int]], n: int, k: int) -> int:
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
heap = [(0, k)]
dist = defaultdict(int)
while heap:
w1, n1 = heapq.heappop(heap)
if n1 in dist:
continue
dist[n1] = w1
for n2, w2 in graph[n1]:
heapq.heappush(heap, (w1 + w2, n2))
return max(dist.values()) if len(dist) == n else -1
# Bellman-Ford
def networkDelayTimeBF(times: List[List[int]], n: int, k: int) -> int:
delay = {i: float("inf") for i in range(1, n + 1)}
delay[k] = 0
for _ in range(n - 1):
for u, v, t in times:
delay[v] = min(delay[v], delay[u] + t)
max_delay = max(delay.values())
return max_delay if max_delay < float("inf") else -1
# |--------------|-----------|--------|
# | Approach | Time | Space |
# |--------------|-----------|--------|
# | Dijkstra | O(E*logV) | O(V+E) |
# | Bellman-Ford | O(E*V) | O(V) |
# |--------------|-----------|--------|
if __name__ == "__main__":
times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]]
n = 4
k = 2
print(networkDelayTime1(times, n, k)) # 2
print(networkDelayTime2(times, n, k)) # 2
print(networkDelayTimeBF(times, n, k)) # 2
#include <algorithm>
#include <cassert>
#include <climits>
#include <queue>
#include <vector>
using namespace std;
class NetworkDelayTime {
public:
// single-source, non-negative weight -> Dijkstra's
// https://leetcode.cn/problems/network-delay-time/solutions/2668220/liang-chong-dijkstra-xie-fa-fu-ti-dan-py-ooe8/
int dijkstra(vector<vector<int>>& times, int n, int k) {
vector<vector<pair<int, int>>> graph(n + 1);
for (auto& t : times) {
graph[t[0]].push_back({t[1], t[2]});
}
vector<int> dist(n + 1, INT_MAX);
// min heap
priority_queue<pair<int, int>, vector<pair<int, int>>,
greater<pair<int, int>>>
min_heap;
dist[k] = 0;
min_heap.push({0, k}); // [dist, node]
while (!min_heap.empty()) {
auto [d, u] = min_heap.top();
min_heap.pop();
if (d > dist[u]) continue; // found the shortest
for (auto& [v, w] : graph[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
min_heap.push({dist[v], v});
}
}
}
int res = 0;
for (int i = 1; i <= n; ++i) {
if (dist[i] == INT_MAX) return -1;
res = max(res, dist[i]);
}
return res;
}
// single source -> Bellman-Ford
int bellman_ford(vector<vector<int>>& times, int n, int k) {
vector<int> dist(n + 1, INT_MAX);
dist[k] = 0;
for (int i = 1; i <= n - 1; i++) {
for (auto& edge : times) {
int u = edge[0], v = edge[1], t = edge[2];
if (dist[u] != INT_MAX && dist[v] > dist[u] + t) {
dist[v] = dist[u] + t;
}
}
}
int res = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] == INT_MAX) return -1;
res = max(res, dist[i]);
}
return res;
}
};
int main() {
NetworkDelayTime solution;
vector<vector<int>> times = {{2, 1, 1}, {2, 3, 1}, {3, 4, 1}};
assert(solution.dijkstra(times, 4, 2) == 2);
assert(solution.bellman_ford(times, 4, 2) == 2);
return 0;
}
787. Cheapest Flights Within K Stops¶
-
Tags: Dynamic Programming, Depth First Search, Breadth First Search, Graph, Heap Priority Queue, Shortest Path
"""
- Return the cheapest price from `src` to `dst` with at most `K` stops.
<iframe width="560" height="315" src="https://www.youtube.com/embed/5eIK3zUdYmE?si=aBR0VbHXTgNuVlGz" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
"""
import heapq
from collections import defaultdict
from typing import List
# Bellman-Ford
def findCheapestPriceBF(
n: int, flights: List[List[int]], src: int, dst: int, k: int
) -> int:
prices = [float("inf") for _ in range(n)]
prices[src] = 0
for _ in range(k + 1):
temp = prices[:]
for u, v, w in flights:
temp[v] = min(temp[v], prices[u] + w)
prices = temp
return prices[dst] if prices[dst] != float("inf") else -1
# Dijkstra
def findCheapestPriceDijkstra(
n: int, flights: List[List[int]], src: int, dst: int, k: int
) -> int:
graph = defaultdict(list)
for u, v, w in flights:
graph[u].append((v, w))
heap = [(0, src, 0)] # (price, city, stops)
visited = defaultdict(int) # {city: stops}
while heap:
price, city, stops = heapq.heappop(heap)
if city == dst:
return price
if stops > k:
continue
if city in visited and visited[city] <= stops:
continue
visited[city] = stops
for neighbor, cost in graph[city]:
heapq.heappush(heap, (price + cost, neighbor, stops + 1))
return -1
# |------------|------------------|---------|
# | Approach | Time | Space |
# |------------|------------------|---------|
# |Bellman-Ford| O(k * E) | O(n) |
# | Dijkstra | O(E * log(V)) | O(n) |
# |------------|------------------|---------|
n = 4
flights = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]]
src = 0
dst = 3
k = 1
print(findCheapestPriceBF(n, flights, src, dst, k)) # 700
print(findCheapestPriceDijkstra(n, flights, src, dst, k)) # 700
#include <cassert>
#include <climits>
#include <queue>
#include <vector>
using namespace std;
class FindCheapestPrice {
public:
int bellman_ford(int n, vector<vector<int>>& flights, int src, int dst,
int k) {
vector<int> dist(n, INT_MAX);
dist[src] = 0;
for (int i = 0; i <= k; ++i) {
vector<int> temp(dist);
for (auto& flight : flights) {
int u = flight[0], v = flight[1], w = flight[2];
if (dist[u] != INT_MAX && dist[u] + w < temp[v]) {
temp[v] = dist[u] + w;
}
}
dist = temp;
}
return dist[dst] == INT_MAX ? -1 : dist[dst];
}
int dijkstra(int n, vector<vector<int>>& flights, int src, int dst, int k) {
vector<vector<pair<int, int>>> graph(n);
for (auto& flight : flights) {
graph[flight[0]].push_back({flight[1], flight[2]});
}
priority_queue<array<int, 3>, vector<array<int, 3>>,
greater<array<int, 3>>>
min_heap;
min_heap.push({0, src, k + 1});
while (!min_heap.empty()) {
auto [cost, u, stops] = min_heap.top();
min_heap.pop();
if (u == dst) {
return cost;
}
if (stops > 0) {
for (auto& [v, w] : graph[u]) {
min_heap.push({cost + w, v, stops - 1});
}
}
}
return -1;
}
};
int main() {
FindCheapestPrice solution;
int n = 4;
vector<vector<int>> flights = {
{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
int src = 0, dst = 3, k = 1;
assert(solution.bellman_ford(n, flights, src, dst, k) == 700);
assert(solution.dijkstra(n, flights, src, dst, k) == 700);
return 0;
}