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

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

Runtime

O(V^2) when using an array implementation, or O((V + E) log V) when using a priority queue

Visualization

Pseudocode

Make a unexplored list and put the starting node in it
Make a map of explored nodes
Make a map of distances from the start and set start to 0

while the unexplored has items in it
	pick the unexplored node with the lowest cost to get to
	set that node to explored
	if that node is the target return its dist from the start
	if not, for each adjacent unexplored node
		calculate the dist from the start (current dist + cost of vertex)
		if this value is less then the current dist, update it
		add the node to the unexplored list
	If you got here, the node is unreachable

Code

import heapq

def dijkstra(start, target, graph):
    if target not in graph:
        return -1

    dists = {start: 0}
    heap = [(0, start)]  # (distance, node)

    while heap:
        dist, key = heapq.heappop(heap)
        if key == target:
            return dist

        for next_key, cost in graph[key].adjacent:
            new_dist = dist + cost
            if new_dist < dists.get(next_key, float('inf')):
                dists[next_key] = new_dist
                heapq.heappush(heap, (new_dist, next_key))

    return -1