void+Dijkstra(Vertex*+Head,+int+n,+int+s,+int+dist[],int+path[]){ int+S[N],i,+j,+min,+v,+w;+for+(i+=
时间: 2024-03-01 12:48:45 浏览: 22
void Dijkstra(Vertex* Head, int n, int s, int dist[], int path[]) {
int S[N], i, j, min, v, w;
for (i = 0; i < n; i++) {
dist[i] = INFINITY; // 初始化距离为无穷大
S[i] = 0; // 初始化集合S为空集
}
dist[s] = 0; // 起始点到自身的距离为0
for (i = 0; i < n; i++) {
min = INFINITY; // 初始化最小距离为无穷大
for (j = 0; j < n; j++) {
if (S[j] == 0 && dist[j] < min) { // 在集合S之外找到距离最小的顶点
min = dist[j];
v = j;
}
}
S[v] = 1; // 将顶点v加入集合S
for (w = 0; w < n; w++) {
if (S[w] == 0 && dist[v] + G[v][w] < dist[w]) { // 更新其他顶点的最短距离
dist[w] = dist[v] + G[v][w];
path[w] = v; // 记录路径
}
}
}
}
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)