计算最短路径的Dijkstra算法的编程实现
实验环境: C++
为了进行网络最短路径路径分析，需将网络转换成有向图。
如果要计算最短路径，则权重设置为两个节点的实际距离，Dijkstra算法可以用于计算从有向图中任意一个节点到其他节点的最短路径。
算法描述：
1）用带权的邻接矩阵来表示带权的n个节点的有向图，road[i][j]表示弧< vertex i, vertex j>的权值，如果从vertex i到vertex j不连通，则road road[i][j]=无穷大=9999。
引进一个辅助向量Distance，每个Distance[i]表示从起始点到终点vertex i的最短路径长度。
设起始点为first，则Distance[i]= road[first][i]。
令S为已经找到的从起点出发的最短路径的终点的集合。
2）选择vertex j使得Distance[j]=Min{ Distance[i]| vertexi∈V-S},vertex j就是当前求得的一条从起始点出的的最短路径的终点的，令S=S∪{ vertex j}
3）修改从起始点到集合V-S中任意一个顶点vertex k的最短路径长度。
如果Distance[j]+ road[j][k]< Distance[k]，则修改Distance[k]为：Distance[k]= Distance[j]+ road[j][k]。
4）重复2,3步骤操作共n-1次，由此求得从起始点出发到图上各个顶点的最短路径长度递增的序列。
算法复杂度为O(n2)。
程序代码如下：
#include <stdio.h>
#include "Dijkstra.h"
int main()
{
int Graph_list_search[max][max]={{0,3,2,5,9999,9999},
{9999,0,9999,2,9999,9999},
{9999,9999,0,1,9999,9999},
{9999,9999,9999,0,9999,5},
{9999,9999,5,3,0,1},
{9999,9999,9999,9999,9999,0}};
printf_edge(Graph_list_search);
Dijkstra(Graph_list_search,0,5);
return 0;
}
以上部分粘贴到记事本以Dijkstra.cpp保存
#define max 6
int find_minimum_route(int route[100],int visit[100],int *position,int vertex_number)
{
int i;
int tag=0;
int temp;
i=0;
temp=9999;
while(i<vertex_number)//route[i]!='\0'
{
if((temp>route[i])&&visit[i]==0)
{
temp=route[i];
*position=i;
tag=1;
}
i++;
}
if(tag=1)return temp;
else
{
*position=vertex_number;
return 9999;
}
}
void Dijkstra(int Graph_list_search[max][max],int first,int end){ int i;
int Graph_minimum_Distance[max];
int Graph_visit[max];
int Graph_minimum_road[max][max];
for(i=0;i<max;i++)
{
Graph_minimum_Distance[i]=Graph_list_search[first][i];
Graph_visit[i]=0;
for(int w=0;w<max;++w)
Graph_minimum_road[i][w]=0;//store the road
if(Graph_minimum_Distance[i]<9999){
Graph_minimum_road[i][first]=1;
Graph_minimum_road[i][i]=1;
}
}
int position;
int minimum_Distance;
Graph_minimum_Distance[first]=0;
Graph_visit[first]=1;
for(int h=1;h<max;h++){
minimum_Distance=find_minimum_route(Graph_minimum_Distance,Graph_visi t,&position,max);
Graph_visit[position]=1;
for(i=0;i<max;i++){
if(Graph_visit[i]==0){
if(Graph_minimum_Distance[i]>minimum_Distance+Graph_list_search[posit ion][i]){
Graph_minimum_Distance[i]=minimum_Distance+Graph_list_search[position ][i];
for(int j=0;j<max;j++)
Graph_minimum_road[i][j]=Graph_minimum_road[position][j]; Graph_minimum_road[i][i]=1;
}
}
}//while(i<max)
}
printf("The minimum road is(vertex%d->vertex%d):\n",first,end); for(i=0;i<max&&printf("->");i++){
if(Graph_minimum_road[end][i]==1)printf("vertex%d",i);
}
printf("\n");
}
void printf_edge(int Graph_list_search[max][max])
{
printf("The example edge is:\n");
for(int i=0;i<max;i++){
for(int j=0;j<max;j++)
printf("%d ",Graph_list_search[i][j]);
printf("\n");
}
}
以上部分粘贴到记事本以Dijkstra.h保存在同一文件夹
运行结果：。