void ShortestPath_DIJ(AMGraph &G, int v0) { //用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径 int n=G.vexnum; //n为G中顶点的个数 int S[n],D[n]; int min,v; for(v = 0; v<n; ++v) //n个顶点依次初始化 { S[v] = false; //S初始为空集 D[v] = G.arcs[v0][v]; //将v0到各个终点的最短路径长度初始化 if(D[v]< MaxInt) Path [v]=v0; //v0和v之间有弧,将v的前驱置为v0 else Path [v]=-1; //如果v0和v之间无弧,则将v的前驱置为-1 }//for S[v0]=true; //将v0加入S D[v0]=0; //源点到源点的距离为0 //―开始主循环,每次求得v0到某个顶点v的最短路径,将v加到S集 for(int i=1;i<n; ++i) //对其余n-1个顶点,依次进行计算 { min= MaxInt; for(int w=0;w<n; ++w) if(!S[w]&&D[w]<min) {v=w; min=D[w];} //选择一条当前的最短路径,终点为v S[v]=true; //将v加入S for(int w=v0;w<n; ++w) //更新从v0出发到集合V?S上所有顶点的最短路径长度 if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])) { D[w]=D[v]+G.arcs[v][w]; //更新D[w] Path[w]=v; //更改w的前驱为v }//if if(G.vexs[i] == vend){ cout<<D[i]<<endl; PrintPath(v,v0,Path); return ; } }//for }//ShortestPath_DI
时间: 2023-11-24 20:06:34 浏览: 91
ShortestPath_DIJ.rar_ShortestPath_DIJ_shortestPath_d_shortestpat
在上述代码的基础上,我们可以按照上面所说的方式来输出中间任意两点之间的最短路径。具体来说,我们可以将 PrintPath 函数修改为一个新的函数,比如 PrintShortestPath,用来输出任意两点之间的最短路径。以下是修改后的代码示例:
```
void PrintShortestPath(int v, int v0, int Path[]) {
if (v == v0) {
cout << v0 << " ";
return;
}
PrintShortestPath(Path[v], v0, Path);
cout << v << " ";
}
void ShortestPath_DIJ(AMGraph &G, int v0, int v) {
// 用Dijkstra算法求有向网G的v0顶点到v顶点的最短路径
int n = G.vexnum; // n为G中顶点的个数
int S[n], D[n], Path[n];
int min, u;
for (u = 0; u < n; ++u) // n个顶点依次初始化
{
S[u] = false; // S初始为空集
D[u] = G.arcs[v0][u]; // 将v0到各个终点的最短路径长度初始化
if (D[u] < MaxInt)
Path[u] = v0; // v0和u之间有弧,将u的前驱置为v0
else
Path[u] = -1; // 如果v0和u之间无弧,则将u的前驱置为-1
}// for
S[v0] = true; // 将v0加入S
D[v0] = 0; // 源点到源点的距离为0
// ―开始主循环,每次求得v0到某个顶点u的最短路径,将u加到S集
for (int i = 1; i < n; ++i) // 对其余n-1个顶点,依次进行计算
{
min = MaxInt;
for (int w = 0; w < n; ++w)
if (!S[w] && D[w] < min)
{
u = w; min = D[w];
} // 选择一条当前的最短路径,终点为u
S[u] = true; // 将u加入S
for (int w = 0; w < n; ++w) // 更新从v0出发到集合V-S上所有顶点的最短路径长度
if (!S[w] && (D[u] + G.arcs[u][w] < D[w]))
{
D[w] = D[u] + G.arcs[u][w]; // 更新D[w]
Path[w] = u; // 更改w的前驱为u
} // if
if (u == v) {
cout << "Shortest distance from " << v0 << " to " << v << ": " << D[u] << endl;
cout << "Shortest path: ";
PrintShortestPath(v, v0, Path);
return;
}
} // for
}
```
在上述代码中,我们增加了一个新的函数 PrintShortestPath,用来输出任意两点之间的最短路径。函数参数包括当前节点 v、起点 v0 和前驱节点数组 Path。该函数的实现方式与上面所说的方式类似,即从终点开始回溯前驱节点,输出路径。同时,我们修改了原来的 ShortestPath_DIJ 函数,增加了一个终点参数 v,并且在找到终点时,输出最短路径和距离。最后,我们在函数中调用 PrintShortestPath 函数,输出任意两点之间的最短路径。
阅读全文