本文记录一下dijkstra算法的实现，图用邻接矩阵表示，假设图为无向图，并且连通，有向图，不连通图的做法类似。
算法简述：
首先确定“单源”的源，假设是第0个顶点。
维护三个数组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，与数组给出的顺序是逆序。
依次从dist[]数组中选一个最小的dist值，假设顶点的坐标为index，这个dist值即为最终确定的最短距离的点，更新这个点的color值为1，下面一个操作是dijkstra算法的重点，也只有这么一个重点操作，即：在没有确定最短距离的集合中(即color值为0的点的集合),如果源点到index的距离，加上index到这些点的距离小于原来的dist值，则更新dist值，，同时更新path值。
重复第3个操作，直到color值为0的集合为空。
下面给出c语言实现代码，方法都出了注释，这里不再说明, 如果不足之处请提出（使用的默认的图如下）：
n;int source = 0;//求从第0个节点到其他节点的最短路径int* dist;int* path;** 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;elsematrix[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);(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] = (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;}
运行结果如下：
三亚呀——赴一个蓝天碧海。
