Shortest Path Algorithm

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

from collections import defaultdict
import heapq

# undirected graph
# edge: [src, dst, weight]

def find_shortest_path(edges, src, dst):
    graph = defaultdict(dict)
    for a, b, weight in edges:
        graph[a][b] = weight
        graph[b][a] = weight
    FindSet = set([])
    distance = [(0, src)]
    while distance:
        weight, vertice = heapq.heappop(distance)
        if vertice == dst:
            return weight
        if vertice in FindSet:
            continue
        FindSet.add(vertice)
        for n_vertice, n_weight in graph[vertice].items():
            if n_vertice in FindSet:
                continue
            heapq.heappush(distance, (weight+n_weight, n_vertice))
    return -1


# directed graph
def find_shortest_path(edges, src, dst):
    graph = defaultdict(dict)
    for a, b, weight in edges:
        graph[a][b] = weight
    distance = [(0, src)]
    while distance:
        weight, vertice = heapq.heappop(distance)
        if vertice == dst:
            return weight
        for n_vertice, n_weight in graph[vertice].items():
            heapq.heappush(distance, (weight+n_weight, n_vertice))
    return -1