Python DFS vs BFS vs Djikstra's(Flavor or BFS)
\nfrom collections import defaultdict\nimport heapq\nfrom collections import deque\nclass Solution:\n    def networkDelayTime(self, times: List[List[int]], n: i
```\nfrom collections import defaultdict\nimport heapq\nfrom collections import deque\nclass Solution:\n    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n\t\n        # Common code for all\n\t\t\n        graph = defaultdict(list)\n        for u, v , w in times:\n            graph[u].append((w,v))\n            \n        dist = {node: float(\'inf\') for node in range(1,n+1)}\n\n# DFS\n        def dfs(node, elapsed):\n            if elapsed >= dist[node]: return # Recursion hence base case,\n            # If elapsed time > the optimal distance in dist[node]\n                #We break\n            # If its equal\n                # we still break\n            dist[node] = elapsed\n            for time, nei in sorted(graph[node]):\n                # Why Sorted? --> Does TLE otherwise, \n                # It is a greedy Strategy, It is not neccessarily required in DFS\n                \n                # To speed things up, at each visited node we\'ll consider signals exiting the node that are faster first, by sorting the edges.\n                dfs(nei, elapsed + time)\n\n        dfs(k, 0)\n        ans = max(dist.values())\n        #print(dist)\n        return ans if ans < float(\'inf\') else -1\n\n\n\n# QUEUE\n        \n        pq = deque() # Queue\n        pq.appendleft((0,k))\n        dist = [float(\'inf\') for _ in range(1, n+2)]\n        dist[k]=0\n        \n        while pq:\n            elapsed_time, node = pq.popleft()\n            for time, nei in graph[node]:\n                    if elapsed_time + time < dist[nei]:\n                        dist[nei] = elapsed_time + time\n                        pq.appendleft((elapsed_time + time,nei))\n        ans = max(dist[1:])\n        print(dist)\n        return ans if ans < float(\'inf\') else -1\n                        \n# Dijkstra\'s Algorithm    \n            \n        pq = [(0,k)]\n        dist = {} # visit all nodes with weight so hashmap works...\n        \n        while pq:\n            elapsed_time, node = heapq.heappop(pq) # always select shortest weight from graph\n            if node not in dist:\n                dist[node] = elapsed_time\n                for nei, time in graph[node]:\n                    if nei not in dist:\n                        heapq.heappush(pq,(time + elapsed_time,nei))\n                        \n        return max(dist.values()) if len(dist) == n else -1\n```\n\nThis resource gives you an understanding of  how Djikstra\'s is actually just a flavor of BFS\nhttps://devtut.github.io/algorithm/dijkstras-algorithm.html#dijkstra-s-shortest-path-algorithm\n\nIt is a no-brainer for all newbies and advanced leetcoders to use\nBFS as the strategy for shortest path. \n**Shortest path ---> BFS** Be it single source, from specific vertex / overall top-bottom in tree-like\n\nWhy BFS over Djikstra\'s \n* We are considering non-negative/ postive weighted graphs*\n1. BFS used on **unweighted** graph --> Treats each edge of same weight\n\t\ta. We can still use BFS and store the cost/ elapsed time in a tuple.\n\t\tb.  Visit 1 hop away nodes. \n\t\tc. Next hop away nodes.\n2. Djikstra\'s  used on Weighted graph (positve weighted only)\n3. We can use DFS which is teh slowest of the three and offer slight optimization by picking fast exiting nodes by sorting the distances.\n\nThese above axioms are just best practices for getting best Complexity!!\nNo body can tell you, that you can\'t implement anything a certain way..\nIf you want to get better though, start chewing more than you can swallow and then get comfortable taking bigger bites\n\n\nVanilla BFS, apart from being utterly vanilla, causes  double updates --> More computation\n*Reasoning here *--> https://devtut.github.io/algorithm/dijkstras-algorithm.html#dijkstra-s-shortest-path-algorithm\n\nDjikstras uses Greedy strategy to pick and "Update" the optimal distance in each step.\nand uses\'s priority queue to pick the smallest weight from current_node.\nTo relax/update and push to the queue...\n\nThis greedy strategy somehow reduces the # updates  make the algo faster...\n\n\nGraph Algorithms are quite philosophical if you think about them..\nDFS:  You start from 0, see each choice to completion --> You will get to your goal, eventually.\nBFS:   You start from 0, see each choice  just 1 hop away ----->>>\n\t\t\t\t\t\t---------> If it fits your constraints/ you go to the next level or you abandon that path. Who knows the right *HOP*, will help you reach your dest quickly, as if by magic!  \nNaaw Son, it Aint Magic, Its Logic. :P\nDjikstra\'s :  Lets Optimized the Magic from BFS shall we ? You start same as BFS, just selectively chose your hops... Increasing probability for that magically hop, all the while reducing effort and knowing fully that, even as we try to be greedy and careful with our energy and updates some situations will be no better the vanilla BFS. \nMagic Arrives on its own time. \nIn some problems all distances have to be traversed. All Vertices to be visited. \nThere is no easy Pruning and result.\nWe have to see all things through..just like the distances to all the vertices from source, where you are at currently. How smartly you do it is upto you ^_^\n\nIgnore my post guys, Just ranting\n\t\t\t\n\t\t\t\n
['Depth-First Search', 'Breadth-First Search', 'Recursion', 'Python']