算法——最短路径算法(dijkstra)-526互联

source 源端， target目的端
1.构造n*n的相邻矩阵， -1表示未相邻
int matrix[n][n]

int  dist[n]  初始化各节点直接到source的距离， dist[source] = 0;
bool visited[n]  是否访问过

    dist[source] = 0;
    for(int i = 0;i<n-1;i++) {
    //找剩余n-1个节点的距离
        int min = INT32_MAX;
        int midx = 0;
        for(int j = 0;j<n;j++){
        //对每个节点判断是否已访问，并找到未访问的距离最短的点
            if (!visited[j] && dist[j] < min){
                min = dist[j];
                midx = j;
            }
        }
        visited[midx] = true;
        dist[midx] = min;
      //对未被访问的节点，通过midx节点为桥梁，更新dist数组
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && matrix[midx][j] > 0){
                dist[j] = min(dist[j], dist[midx] + matrix[midx][j]);
            }
        }
      //不断访问节点，直到所有节点都访问过后，退出循环。
    }