#define MAX_VERTEX_NUM 100 //最大顶点数
#define MAX_INT 10000 //无穷大
typedef int AdjType;
typedef struct{
int
pi[MAX_VERTEX_NUM];//存放v到vi的一条最短路径
int
end;
}PathType;
typedef char VType; //设顶点为字符类型
typedef struct{
VType
V[MAX_VERTEX_NUM]; //顶点存储空间
AdjType
A[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
}MGraph;//邻接矩阵表示的图
//Dijkstra算法
//求G（用邻接矩阵表示）中源点v到其他各顶点最短路径,n为G中顶点数
void Dijkstra(MGraph * G,PathType path[],int dist[],int v,int
n){
int
i,j,count,s[n],max,u;//s[n]用来标志源点到某顶点的最短路径是否求出
for(i=0;i
s[i]=0;
dist[i]=G->A[v][i];//v到其他顶点的权为当前最短路径，送dist[i]
path[i].pi[0]=v;path[i].end=0;
}
dist[v]=0;
s[v]=1;//源点到源点本身的最短路径求出
count=1;
while(count<=n-1){//求n-1条最短路径
max=MAX_INT;//
MAX_INT为无穷大值，需要实际情况设置
for(j=0;j
if(s[j]==0&&dist[j]
u=j;
max=dist[j];
}
}
if(max==MAX_INT)break;//最短路径求完（不足n-1）条，跳出while循环
s[u]=1;//表示V到Vu最短路径求出
path[u].end++;
path[u].pi[path[u].end]=u;
for(j=0;j
if(s[j]==0&&dist[j]>dist[u]+G->A[u][j]){
dist[j]=dist[u]+G->A[u][j];
path[j]=path[u];
}
}
count++;
}
}
int main(){
int
i,j,v=0,n=6;//v为起点，n为顶点个数
MGraph
G;
PathType path[n];//v到各顶点的最短路径向量
int
dist[n];//v到各顶点最短路径长度向量
AdjType
a[MAX_VERTEX_NUM][MAX_VERTEX_NUM]={
{MAX_INT,12,18,MAX_INT,17,MAX_INT},
{12,MAX_INT,10,3,MAX_INT,5},
{18,10,MAX_INT,MAX_INT,21,11},
{MAX_INT,3,MAX_INT,MAX_INT,MAX_INT,8},
{17,MAX_INT,21,MAX_INT,MAX_INT,16},
{MAX_INT,5,11,8,16,MAX_INT}
};
for(i=0;i
for(j=0;j
G.A[i][j]=a[i][j];
}
}
Dijkstra(&G,path,dist,v,n);
for(i=0;i
printf("%d到%d的最短路径:",v,i);
for(j=0;j<=path[i].end;j++){
printf("%d ",path[i].pi[j]);
}
printf("\n");
printf("最短路径长度:%d",dist[i]);//输出为MAX_INT则表示两点间无路径
printf("\n");
}
system("pause");
return
0;
}
加载中，请稍候......
加载中…
喜欢