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.
[code] 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 [/code]