[数据结构与算法]Dijkstra算法 C语言实现---数据结构图论算法

算法思想

维护三个数组，

• 一个visited数组，表示是否已经划入最短路径
• 一个lowcost数组，表示从初始节点到达各个节点的最小代价
• 一个path数组，用来存放最短路径，path[i]代表节点i的前驱节点，根据不断寻找前驱节点可以描述整个路径。

思想类似于Prim算法，使用贪心的策略，每次从lowcost数组中选择最小值归入最短路径，并且根据已经并入的节点更新lowcost数组，具体细节可见代码。

代码

使用临界矩阵存储为例，代码如下

#define MAX_VEXNUM 100
typedef struct{
    int edge[MAX_VEXNUM][MAX_VEXNUM];
    int vex[MAX_VEXNUM];
    int vexnum,edgenum;
}MGraph;//邻接矩阵存储图
void Dijkstra(MGraph G,int v0;int *path){
    int visited[MAX_VEXNUM];//访问数组
    int lowcaost[MAX_VEXNUM];//最小代价数组
    // int path[MAX_VEXNUM];//路径数组，存储从v0到当前节点的路径上，当前节点的前一个节点
    // 将path作为参数传进，得到最短路径
    for(int i=0;i<G.vexnum;i++){//初始化
        visited[i]=0;
        lowcaost[i]=G.edge[v0][i];
        path[v0]=-1;
    }
    visited[v0]=1;
    int pre=v0;//路径上的前序节点
    for(int i=0;i<G.vexnum-1;i++){//进行n-1轮lowcost的选择，贪心算法
        int min=MAX_INT,index;
        for(int j=0;j<G.vexnum;j++){//从lowcost数组中找出最小值
            if(!visited[j]&&lowcaost[j]<min){
                min=lowcaost[j];
                index=j;//记录最小值下来
            }
        }
        path[index]=pre;
        pre=index;
        for(int i=0;i<G.vexnum;i++){//更新代价数组，这里与Prim不同
            if(!visited[i]&&lowcaost[i]+G.edge[index][i]<lowcaost[i]){
                lowcaost[i]=lowcaost[i]+G.edge[index][i];
            }
        }
    }
    return;
}

与Prim算法进行比较

和Prim的不同之处在于图上标示位置，即更新代价数组时，Dijkstra算法比较lowcaost[i]+G.edge[index][i]和lowcaost[i]并选最小值更新，而Prim算法为比较G.edge[index][j]与lowcaost[j]并选最小值更新！
Prim在于寻找集合间的最小代价，而Dijkstra在于寻找某个节点到其余节点的最小代价
可以参考另一篇Prim算法https://blog.csdn.net/Sherlockfei/article/details/120941295