Dijkstra算法的简单实现

Dijkstra算法用于求解最短路径问题，下面是python语言的简单实现：

def dijkstra(start, graph):
    passed = [start]
    no_pass = [x for x in range(len(graph)) if x != start]
    dis = graph[start]

    while len(no_pass):
        idx = no_pass[0]  # 此时略过了本身(0, 0), 选取(0, 1) - (0, 5)中的最小值
        for i in no_pass:
            if dis[i] < dis[idx]:
                idx = i

        no_pass.remove(idx)
        passed.append(idx)

        for i in no_pass:
            # 如果A-B的距离+B-C距离<A-C的距离，将A-C的距离替换为(A-B + B-C)，此时为A-C的最短路径
            if dis[idx] + graph[idx][i] < dis[i]:
                dis[i] = dis[idx] + graph[idx][i]
    return dis


if __name__ == "__main__":
    inf = 999
    matrix = [[0, 1, 12, inf, inf, inf],
              [inf, 0, 9, 3, inf, inf],
              [inf, inf, 0, inf, 5, inf],
              [inf, inf, 4, 0, 13, 15],
              [inf, inf, inf, inf, 0, 4],
              [inf, inf, inf, inf, inf, 0]]

    res = dijkstra(0, matrix)
    print(res)