Description

Dijkstra's Algorithm is a method for finding the distance to a node, when each vertex has a cost associated with it. It is a variation of the Breadth First Search but it uses a Heap

Note: if you have negative weights you need to use Bellman-Ford algorithm

Runtime

O((V + E) log V) with a min-heap (O(V²) with an array)

Visualization

Pseudocode

Add the start node to a min-heap, with distance 0
While there is a value in the heap
	Pop the node with the smallest distance
	If the node is the one we are looking for, return its distance
	If it is not,
		For each neighbor, new distance = current distance + edge cost
		If that beats the neighbor's best distance so far,
			update it and add the neighbor to the heap
If the heap is empty and you didnt find it, there is no path to it.

Code

import heapq

def dijkstra(start, target, graph):
    dists = {start: 0}
    heap = [(0, start)]

    while heap:
        dist, key = heapq.heappop(heap)
        if key == target:
            return dist
        for node, cost in graph[key].neighbors:
            new_dist = dist + cost
            if new_dist < dists.get(node, float('inf')):
                dists[node] = new_dist
                heapq.heappush(heap, (new_dist, node))
    return -1