void Dijkstra(int v0,int s) //迪杰斯特拉求最短路径,并输出路线 { int min,i,j,u,v; int p[110],l[110]; memset(p,-1,sizeof(p)); memset(l,0,sizeof(l)); memset(book,0,sizeof(book)); for(i=1;i<=18;i++) { dis[i]=map[v0][i]; if(dis[i]<inf) //v0能直接到达,即上一站点为v0 p[i]=v0; } book[v0]=1; for(i=1;i<18;i++) { min=inf; for(j=1;j<=18;j++) //每次找出距离v0最近点 { if(book[j]==0&&dis[j]<min) { min=dis[j]; u=j; } } book[u]=1; //标记该点 for(v=1;v<=18;v++) { if(book[v]==0&&dis[v]>dis[u]+map[u][v]) //通过最近点更新其他边 { p[v]=u; //存储更新的边,即为路线 dis[v]=dis[u]+map[u][v]; } } } v=s; i=1; while(p[v]!=v0) //将路线存入栈中,正序输出 { l[i++]=p[v]; v=p[v]; } printf("\n"); u=i-1; printf("路线为:\n"); printf("%s--->",q[v0].name); for(i=u;i>=1;i--) printf("%s--->",q[l[i]].name); printf("%s\n",q[s].name); printf("最短路径长度为:%d 米\n",dis[s]); }
时间: 2024-03-08 17:45:14 浏览: 51
这段代码是用迪杰斯特拉算法来求一个图中从起点v0到终点s的最短路径,并输出路径和路径长度。其中,map数组存储了图的邻接矩阵表示,dis数组存储了起点v0到各个点的最短距离,p数组存储了从起点v0到各个点的最短路径上的上一个节点(即路径的前驱节点),book数组用来标记每个点是否已经被访问过。具体实现中,首先初始化dis数组和p数组为起点v0到各个点的距离和路径,然后每次从未标记的点中找出距离起点最近的点u,标记该点,并通过该点更新其他点的距离和路径。最后,根据p数组回溯出从起点v0到终点s的路径,并输出路径和路径长度。
相关问题
C语言迪杰斯特拉求解最短路径问题的代码
C语言中,迪杰斯特拉算法通常用于寻找图中的最短路径。以下是一个简单的迪杰斯特拉算法的示例代码,假设我们有一个邻接矩阵表示的无权图:
```c
#include <stdio.h>
#include <limits.h>
#define V 9 // 图的顶点数
int minDistance(int dist[], bool sptSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
void dijkstra(int graph[V][V], int src) {
int dist[V]; // 初始化距离数组
bool sptSet[V]; // 标记数组,标记已访问过的顶点
// 初始化所有顶点的距离为无穷大,源点距离为0
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
sptSet[i] = false;
}
dist[src] = 0;
// 从源点开始,依次找出与源点相连且未访问过的顶点中距离最短的顶点
for (int count = 0; count < V - 1; ) {
int u = minDistance(dist, sptSet);
sptSet[u] = true; // 标记u为已访问
// 更新其邻居顶点的距离,如果通过u到邻居更近
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX &&
dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
count++;
}
// 打印结果
printf("Vertex \t\t Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}
// 测试用法:邻接矩阵表示图
int main() {
int graph[V][V] = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
dijkstra(graph, 0); // 从顶点0开始搜索最短路径
return 0;
}
```
迪杰斯特拉算法求最短路径
迪杰斯特拉算法是一种用于求解最短路径的经典算法。它可以计算一个节点到其他所有节点的最短路径。下面是一个使用C++实现的迪杰斯特拉算法求最短路径的示例[^1]:
```cpp
#include <iostream>
#include <limits.h>
#define V 9
int minDistance(int dist[], bool sptSet[])
{
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
{
if (sptSet[v] == false && dist[v] <= min)
{
min = dist[v];
min_index = v;
}
}
return min_index;
}
void printSolution(int dist[])
{
std::cout << "Vertex \t\t Distance from Source" << std::endl;
for (int i = 0; i < V; i++)
{
std::cout << i << " \t\t " << dist[i] << std::endl;
}
}
void dijkstra(int graph[V][V], int src)
{
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++)
{
dist[i] = INT_MAX;
sptSet[i] = false;
}
dist[src] = 0;
for (int count = 0; count < V - 1; count++)
{
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
{
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
{
dist[v] = dist[u] + graph[u][v];
}
}
}
printSolution(dist);
}
int main()
{
int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}};
dijkstra(graph, 0);
return 0;
}
```
这段使用邻接矩阵表示图,其中`V`表示节点的数量。通过调用`dijkstra`函数,可以计算从源节点到其他所有节点的最短路径,并将结果打印出来。