单源最短路径 dijkstra算法实现

时间:2022-12-30 08:05:49

  本文记录一下dijkstra算法的实现,图用邻接矩阵表示,假设图为无向图。而且连通,有向图,不连通图的做法相似。

算法简述:

  1. 首先确定“单源”的源。假设是第0个顶点。

  2. 维护三个数组dist[], color[], path[]。设其下标分别为0…i…n-1:

      dist[] 表示源点到顶点i的最短距离,在初始化时,假设源点到顶点i有路径,则初始化为路径的权重。否则初始化为INT_MAX。

      color[] 数组事实上表示两个集合,即color[i]值为1的集合表示已经确定最短路径的点的集合,color[i]值为0表示没有确定最短路径的点的集合。初始化为将源点的color设置为1,其余点设置为0。

      path[]数组存储到顶点i的路径,假设path[i]=3,path[3]=2,paht[2]=0,则这条最短路径是0->2->3->i,与数组给出的顺序是逆序。

  3. 依次从dist[]数组中选一个最小的dist值,假设顶点的坐标为index,这个dist值即为终于确定的最短距离的点,更新这个点的color值为1。以下一个操作是dijkstra算法的重点。也仅仅有这么一个重点操作,即:在没有确定最短距离的集合中(即color值为0的点的集合),假设源点到index的距离,加上index到这些点的距离小于原来的dist值,则更新dist值,同一时候更新path值。

  4. 反复第3个操作,直到color值为0的集合为空。

以下给出c语言实现代码,方法都出了凝视,这里不再说明, 假设不足之处请提出(使用的默认的图例如以下):

单源最短路径 dijkstra算法实现

#include <stdlib.h>
#include <stdio.h>
#include <limits.h> int n;
int source = 0; //求从第0个节点到其它节点的最短路径
int* dist;
int* path;
int* color; //颜色为1说明已经找到最短路径。为-1说明没找到最短路径 //获得默认的图,即上图所看到的。使用邻接矩阵表示
int** get_graph(){
int** matrix;
int i,j;
int start,end,weight; printf("input vertex num:\n");
scanf("%d",&n); matrix = (int**)malloc(sizeof(int*)*n); for(i=0;i<n;i++){
matrix[i] = (int*)malloc(sizeof(int)*n);
for(j=0;j<n;j++){
if(i!=j)
matrix[i][j] = INT_MAX;
else
matrix[i][j] = 0;
}
} printf("input start end weight, stop by -1\n"); for(;;){
scanf("%d",&start);
if(start==-1){
break;
}
scanf("%d %d",&end,&weight);
matrix[start][end] = weight;
matrix[end][start] = weight;
}
return matrix;
} //使用迪杰斯特拉算法求单源最短路径
void single_source_shortest_path(int** matrix,int source){ int i,j,index,min; dist = (int*)malloc(sizeof(int)*n);
color = (int*)malloc(sizeof(int)*n);
path = (int*)malloc(sizeof(int)*n); //初始化最短路径:
//直接相连的初始化为权重,不直接相连的初始化为INT_MAX
for(i=0;i<n;i++){
dist[i] = matrix[source][i];
color[i] = 0;
if(i!=source && dist[i]!=INT_MAX){
path[i] = source;
}else{
path[i] = -1;
}
} color[source] = 1;
path[source] = 0; //找一个从源点到其它节点最短的路径
for(j=0;j<n;j++){
min = INT_MAX;
index = -1;
for(i=0;i<n;i++){
if(!color[i] && dist[i]<min){
index = i;
min = dist[i];
}
} if(index==-1){ //全部定点的终于距离都确定
break;
} color[index] = 1; //标记为已经确定最短距离的定点 //接下来更新到每一个未确定最短距离的定点的距离
//假设源点到刚刚加入的节点的最短距离+刚刚加入的节点的距离到未确定最短距离的定点的距离 < 源最短距离,则更新
for(i=0;i<n;i++){
if(!color[i] && matrix[index][i]!=INT_MAX && dist[index]+matrix[index][i]<dist[i]){
dist[i] = dist[index]+matrix[index][i];
path[i] = index;
}
}
}
} int main(){ int** matrix = get_graph();
int i,t; single_source_shortest_path(matrix,source); printf("\n");
for(i=0;i<n;i++){
printf("%d: %d,and the path is(inverse order): %d ",i,dist[i],i);
t = path[i];
while(1){
printf(" %d ",t);
if(t==0){
break;
}
t = path[t];
}
printf("\n");
} printf("\n");
return EXIT_SUCCESS;
}

执行结果例如以下:

单源最短路径 dijkstra算法实现