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…