After solved 1000 medium leetcode found thes patterns — Dijkstra, Floyd-Warshall, Bellman
Following leetcode patterns . DP ,Backtracking, Mono-stack, Presum, Sliding window, Devide and conquer, Binary Search
This article is to share 3 shortest path finding algorithms . All popular and classic . They got different Time complexity . personally i like Dijkstra most . but good to know different ways to approach the same problem (even they are slow and bit brute force).
Lets start with this problem : Leetcode 1334 : Given node list [0, n] , and edges : [(from, to)..] , Count the reachable cities within distance threshold .
Dijkstra
This is classic algo to find shortest path between every 2 node in a graph . but if you think from DFS approach ,will work but a bit slow :from start node , DFS every edge and as long as the distance between :start node to current node x < until now distance[x] , update the distance , do the same for every node, until finish the whole map .
This solution will time out
def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
g = defaultdict(list)
for e1, e2, v in edges:
g[e1].append((e2, v))
g[e2].append((e1, v))
def count(n, g, dist, d, thres):
if d > thres or dist.get(n, float('inf')) < d:
return
dist[n] = d
for _next, v in g.get(n, []):
count(_next, g, dist, d+v, thres)
res = []
for i in range(n):
dist = {}
count(i, g, dist, 0, distanceThreshold)
res.append((len(dist)-1, i))
res.sort()
min_reach = res[0][0]
return max([r[1] for r in res if r[0] == min_reach])there is one optimal point here, if we can make sure when reach node x, the distance come from other nodes already sorted, so when process the distance will be from short to long, can avoid process “the longer distance come from same node” . this is kind of BFS+heapq , and this is the core idea of dijkstrea . Code like below :
def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
"""
For city : [0, 1, 2 ... n], there are connections :
0--<3>--1
\ / \
<2> <4> <1>
\ / \
-3---<1>---2
So we have graph:
0 : [(1, 3), (2,3)]
1 : [(2, 1), (3, 4)]
2 : [(1, 1), (3, 1)]
3 : [(1, 4), (2, 1)]
Now start from every city, walk as far as possible. find the reachable cities.
use q [(city, cost)] to track .
start from 0 :
[(0, 0)] ->
[(1, 3), (3,2)] ->
[(3,7), (3,2), (2,4), (2,8)]
For city 3 for city 2, we only need to keep the minimum cost . So we need a heap to grantee that
when traverse city X, the cost [(city1, cost1), (city2, cost2)..] are sorted. to filter out the path
come from higher cost city (which already visited by coming from lower cost city).
So the procedure changed into :
[(0, 0)] # cost 0, city 0
[(2, 3), (3, 1)] # sorted by cost
[(2, 3), (4, 2)] # (8, 2), (7,3) are filtered out
If threshold distance is 3, reachable city from city 0 is [3]
Do the same for other cities
"""
thres = distanceThreshold
graph = defaultdict(list)
for e1, e2, d in edges:
graph[e1].append((e2, d))
graph[e2].append((e1, d))
def reachable(x, g):
q = [(0, x)] # to self cost is 0
min_dist = {}
while q :
cost, city = heapq.heappop(q) # make sure check min cost first
if city in min_dist: # already visited by lower cost city
continue
if cost > thres:
continue
min_dist[city] = cost
for n, c in g.get(city, []):
heapq.heappush(q, (cost+c, n))
return len(min_dist)
res = {}
for i in range(n):
res[i] = reachable(i, graph)
min_reachable = min(res.values())
return max([city for city, count in res.items() if count == min_reachable])Floyd-Warshal
Compare to Dijkstra , Floyd algorithm is a bit brute-force .So if we think about from node m to node n, we can either direct reach(by any edge), or “pass by” another node k . the idea is ,let every node [0…n] be the “pass by” node, and enumerate the answer (shortest distance) between node i and node j (to pass by node k). the idea is simple , code is also short but complexity is O(n³) .should be good enough for small input . but personally i prefer Dijstra which is more optimal.
def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
"""
Floyd-Warshall All-Pairs Shortest Path:
For every city k, k: [0, n]. find city i and city j "pass by" .
While passing by , update the distance between city i and city j
loop through all the combinations of [city i, city j] , i: [0, n], j: [0, n]
"""
dist = [[float('inf')] * n for _ in range(n)] # assume no city are connected
for e1, e2, d in edges: # connect city based on edge
dist[e1][e2] = d
dist[e2][e1] = d # indirect graph
for i in range(n):
dist[i][i] = 0 # distance to self is 0
for city_pass in range(n):
for city_from in range(n):
for city_to in range(n):
dist[city_from][city_to] = min(dist[city_from][city_pass]+dist[city_pass][city_to], dist[city_from][city_to] )
thres = distanceThreshold
res = {}
min_count = float('inf')
for i in range(n):
res[i] = len([d for d in dist[i] if d <= thres])
min_count = min(min_count, res[i])
return max([city for city,count in res.items() if count == min_count])Bellman (TLE)
Previous 2 algorithms both forcus on “node”. Bellman–Ford algorithm more focus on “edge”. The idea is when start from node (x) , use 1 edge what is the shortest path to other node, then how about use 2 edges, then use 3edges … use N-1 edges ,then consolid the best answer .
def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
"""
For city : [0, 1, 2 ... n], there are connections :
0--<3>--1
\ / \
<2> <4> <1>
\ / \
3---<1>---2
The Core idea of bellman-ford algo is: use 'X edge' to get shortest distance, X = [1, n]
Start from each city and do the same.
Start from city 0, Use 1 edge : [(0, 1), (0,3)]:
0-------1(3)
\ / \
\ / \
\ / \
3(2)----2(INF)
Again start from 0, use 2 edge : [(0,1)->(1,3) 5>2, not update ; (0,1)->(1,2) got 4;(0,3)-> (3,2) got 3]
0-------1(3)
\ / \
\ / \
\ / \
3(2)----2(3)
Start from 0, use 3 edge : [(0,1)->(1,2)->(2,3) 7>2 , not update; (0,3)->(3,2)->(2,1) not update, same for another path, no update]
So above distance is the answer
"""
def bellman(start, edges, n, thres):
res = [float('inf')]*n
res[start]=0
for x in range(1, n): # max can use n-1 edges
for e1, e2, d in edges:
res[e2] = min(res[e2], res[e1]+d)
res[e1] = min(res[e1], res[e2]+d) # indirect graph
return len([r for r in res if r <= thres])
thres = distanceThreshold
res = {}
min_count = float('inf')
for i in range(n):
res[i] = bellman(i, edges, n, thres)
min_count = min(min_count, res[i])
return max([city for city,count in res.items() if count == min_count])This algorithm is too low : O(N² * M), M=number of edges , result in TLE . again , not recommended but good to know the idea .
Conclusion
When solving shortest path issue, disjstra should be the first solution to think of .
Thanks for reading !
