11_最短路径
- 格式：docx
- 大小：13.02 KB
- 文档页数：2
9.最短路径
//dijkstra
#define MAXVEX 9
#define INFINITY 65535
typedef int Patharc[MAXVEX]; //用于存储最短路径的下标数组typedef int ShortPathTable[MAXVEX]; //用于存储到各点最短路径的权值之和
void ShortestPath_Dijkstar(MGraph G,int V0,Patharc *P,ShortPathTable *D){
int v,w,k,min;
int final[MAXVEX]; //final[w]=1 表示已求得的顶点V0到Vw的最短路径
//初始化数据
for(v=0;v<G.numVertexes;v ++){
final[v] =0; //全部顶点化为未找到的最短路径
(*D)[V] = G.arc[V0][v]; //将与V0有连线的顶点加上权值
(*P)[V] = 0; //初始化路径数组P为0
}
(*D)[V0]=0; //V0到V0的路径为0
final[V0]=1; //V0到V0不需要求路径
//开始主循环，每次求得V0到某个顶点的最短路径
for(v=1;v<G.numVertexes;v++){
min =INFINITY;
for(w=0;w<G.numVertexes;w++){
//从w=1时进入判断
if(!final[w]&&(*D)[w]<min){
k=w;//k的变化就是最短路径的遍历
min = (*D)[w];
}
}
final[k]=1; //将目前的最近顶点置为n 1
//修正当前的最短路径及距离
for(w=0;w<G.numVextexes;w++){
//如果经过V顶点的路径比现在这条路径短的话，更新
//从w=2开始判断
if(!final[w]&&(min+G.arc[k][w])<(*D[w])){
//
(*D)[w] = min + G.arc[k][w];//修改当前路径长度
(*P)[w] = k;//存放前驱顶点
}
}
}
typedef int Patharc[MAXVEX]; //用于存储最短路径的下标数组typedef int ShortPathTable[MAXVEX]; //用于存储到各点最短路径的权值之和
void ShortestPath_Dijkstar(MGraph G,int V0,Patharc *P,ShortPathTable *D){
int v,w,k;
//初始化D和P
for(v=0;v<G.numVertexes;v++){
for(w=0;w<G.numVerexes;v++){
(*D)[v][w]=G.matirx[v][w];
(*P)[v][w]=w;
}
}
//优美的floyd算法
for(k=0;k<G.numVertexes;k++){
for(v=0;v<G.numVertexes;v++){
for(w=0;w<G.numVertexes;k++){
if((*D)[v][w]>(*D)[v][k]+(*D)[k][w]){
(*D)[v][w]=(*D)[v][k]+(*D)[k][w];
//
(*P)[v][w]=(*P)[v][k];
}
}
}
}
}。
