Dijkstra’s algorithm

My version in python. The code is specific to how g, the graph matrix is defined.

Here is a good explanation to why we need to get the vertex with min edge in each iteration.

def graphDistances(g, s):
    INFINITY = 9999999999
    size = len(g)
    dist = [INFINITY] * size
    prev = [None] * size
    unvisited = set(range(size))

    dist[s] = 0

    while unvisited:
        u = findVertexWithMinDist(unvisited, dist)
        unvisited.remove(u)
        for v, edge_weight in enumerate(g[u]):
            if edge_weight == -1:
                continue
            my_dist = dist[u] + edge_weight
            if my_dist < dist[v]:
                dist[v] = my_dist
                prev[v] = u
        
    return dist

def findVertexWithMinDist(unvisited, dist):
    min_val = None
    min_idx = None
    for i in unvisited:
        v = dist[i]
        if min_val is None or v < min_val:
            min_val = v
            min_idx = i
    return min_idx

Ref:
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s