最短路径算法Dijkstra

c++代码：

#include 
#include 
#include 

int main()
{
    int n = 6;
    int a[n][n] = {
     {0, 10, 10000, 4, 10000, 10000},
     {10, 0, 8, 2, 6, 10000},
     {10000, 8, 10, 15, 1, 5},
     {4, 2, 15, 0, 6, 10000},
     {10000, 6, 1, 6, 0, 12},
     {10000, 10000, 5, 10000, 12, 0}
    };
    int dis[n];  // 记录起始节点到其他节点的距离
    memset(dis, 10000, sizeof(dis));  // 刚开始都初始化为：最大值
    for (int i = 0; i < n; i++) {
        dis[i] = a[0][i];
    }

    int v[n];  // 当数组v中的值为0时，代表未访问过，为1时，代表已访问
    memset(v, 0, sizeof(v));  // 刚开始都初始化为：未访问状态

    //从未访问过的节点中，找到离起始节点最短距离的点
    for (int i = 0; i < n; i++) {
        int min_index = 0;
        int min = 10000;
        for (int j = 0; j < n; j++) {
            if (!v[j] && dis[j] < min) {
                min = dis[j];
                min_index = j;
            }
        }
        v[min_index] = 1;
        for (int j = 0; j < n; j++) {
            if (!v[j] && dis[min_index] + a[min_index][j] < dis[j]) {
                dis[j] = dis[min_index] + a[min_index][j];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%ld ", dis[i]);
    }
    printf("n");
}

python代码：

MAX= float('inf')
matrix = [
    [0,10,MAX,4,MAX,MAX],
    [10,0,8,2,6,MAX],
    [MAX,8,10,15,1,5],
    [4,2,15,0,6,MAX],
    [MAX,6,1,6,0,12],
    [MAX,MAX,5,MAX,12,0]
    ]
def dijkstra(matrix, start_node):
    #矩阵一维数组的长度，即节点的个数
    matrix_length = len(matrix)
    #访问过的节点数组
    used_node = [False] * matrix_length
    #最短路径距离数组
    distance = [MAX] * matrix_length
    #初始化，将起始节点的最短路径修改成0
    distance[start_node] = 0
    #将访问节点中未访问的个数作为循环值，其实也可以用个点长度代替。
    while used_node.count(False):
        min_value = float('inf')
        min_value_index = 999
        #在最短路径节点中找到最小值，已经访问过的不在参与循环。
        #得到最小值下标，每循环一次肯定有一个最小值
        for index in range(matrix_length):
            if not used_node[index] and distance[index] < min_value:
                min_value = distance[index]
                min_value_index = index
        #将访问节点数组对应的值修改成True，标志其已经访问过了
        used_node[min_value_index] = True
        #更新distance数组。
        #以B点为例：distance[x] 起始点达到B点的距离，
        #distance[min_value_index] + matrix[min_value_index][index] 是起始点经过某点达到B点的距离，比较两个值，取较小的那个。
        for index in range(matrix_length):
            distance[index] = min(distance[index], distance[min_value_index] + matrix[min_value_index][index])
    return distance
start_node = int(input('请输入起始节点:'))
result = dijkstra(matrix,start_node)
print('起始节点到其他点距离：%s' % result)

• 参考文献
  https://www.bbsmax.com/A/amd0w9V25g/