数据结构-迪杰斯特拉最短路径算法 （C++代码）

解题思路:

输入邻接矩阵时，将0换成INT_MAX便于计算

注意事项:

参考代码:

#include<cstdio>

#include<limits.h>

typedef int vertex;

int map1[50][50];

void initialize(int);

void Dijkstra(vertex,int); 

int main() {

    int vertexNum,start;

    scanf("%d%d", &vertexNum,&start);

    initialize(vertexNum);

    Dijkstra(start, vertexNum);

    return 0;

}

void initialize(int vertexNum) {//初始化

    for(int i=0;i<vertexNum;i++){

        for(int j=0;j<vertexNum;j++){

            scanf("%d",&map1[i][j]);

            if(map1[i][j]==0)

                map1[i][j]=INT_MAX;

        }

    }

}

void Dijkstra(vertex start, int vertexNum) {

    int dist[50];//源点到各个点的距离

    bool visited[50];//该点是否被访问过，避免重复访问

    for (int i = 0;i < vertexNum;i++) {//两个矩阵初始化

        visited[i] = false;

        dist[i] = map1[start][i];

    }

    visited[start] = true;//源点

    while (true) {

        int minVertex = -1;//找出未收录（未访问）且dist最小的点

        int Min = INT_MAX;

        for (int i = 0;i < vertexNum;i++) {

        if (dist[i] < Min&&visited[i] == false) {

        minVertex = i;

        Min = dist[i];

        }

    }

    if (minVertex == -1)break;//没有符合条件的点

    visited[minVertex] = true;

    for (int i = 0;i < vertexNum;i++) {//遍历该点的邻接点并更新dist

        if (map1[minVertex][i] != INT_MAX && dist[i] > dist[minVertex] + map1[minVertex][i]) {

                dist[i] = dist[minVertex] + map1[minVertex][i];

        }

    }

}

for (int i = 0;i < vertexNum;i++){

    if(i!=start){

        if(dist[i]==INT_MAX)

            printf("-1 ");

        else

    printf("%d ", dist[i]);

    }

    }

}