Shortest distance from source node to all the nodes

"""
Problem:
Find shortest distance from source to all nodes in a graph with non-negative weights.

------------------------------------------------------------

Observation:
If we already know the shortest distance to a node,
we can try to improve distances of its neighbors.

Since weights are non-negative,
the node with smallest distance is always correct.

------------------------------------------------------------

Intuition:
Always pick the closest node first and expand from it.

- Maintain dist[] → shortest distance
- Use min-heap → to get closest node
- Relax edges → update neighbor distance if better

If a node appears again in heap with worse distance,
skip it (outdated path).

------------------------------------------------------------

Code Intuition:
- Initialize dist[src] = 0, rest = ∞
- Push (0, src) into heap
- While heap:
    - pop smallest distance node
    - skip if outdated
    - relax all neighbors

------------------------------------------------------------

Time Complexity:
For each time, a verted a popped from the min heap so O(Vlog(V))
for each time, an edge is pushed into the min heap so O(Elog(E))
so total is sum of both ie. O(V+E(logV)) because E=V^2 when all nodes are connected to each other so Elog(E) becomes Elog(V^2) ie. 2Elog(V) ie. Elog(V) so Elog(V)+Vlog(V) equal (E+V)log(V)
"""

from collections import defaultdict
from heapq import heappush,heappop
import math
class Solution:
    # Returns shortest distances from src to all other vertices
    def dijkstra(self, v, edges, src):
        graph=defaultdict(list)
        for a,b,c in edges:
            graph[a].append((b,c))
            graph[b].append((a,c))
        # print(graph)
        dist=[math.inf]*v
        dist[src]=0
        heap=[]
        heappush(heap,(0,src))
        while len(heap)>0:
            cur_dis,node=heappop(heap)
            if cur_dis>dist[node]: #this stops going back to the same node but the dist to go to the same node is less now.In djktra same node can come in the heap multiple times so the other route already distance less so no need to consider this route.
                continue
            for neigh, w in graph[node]:
                if cur_dis+w< dist[neigh]:
                    dist[neigh]=cur_dis+w
                    heappush(heap,(cur_dis+w, neigh))
        return dist