无向网迪杰斯特拉算法代码示例
时间: 2023-03-26 12:02:38 浏览: 49
以下是无向网迪杰斯特拉算法的代码示例:
```
#define MAXVEX 100 // 最大顶点数
#define INFINITY 65535 // 用65535来代表无穷大
typedef int Patharc[MAXVEX]; // 存储最短路径下标的数组
typedef int ShortPathTable[MAXVEX]; // 存储到各点最短路径的权值和
void ShortestPath_Dijkstra(MGraph G, int v, Patharc *P, ShortPathTable *D) {
int v, w, k, min;
int final[MAXVEX]; // final[w] = 1 表示已经求得v到w的最短路径
for (v = ; v < G.numVertexes; v++) {
final[v] = ; // 初始化
(*D)[v] = G.arc[v][v]; // 初始化最短路径权值为v到各点的权值
(*P)[v] = ; // 初始化路径数组P为
}
(*D)[v] = ; // v到v的路径为
final[v] = 1; // v到v不需要求路径
// 开始主循环,每次求得v到某个v顶点的最短路径
for (v = 1; v < G.numVertexes; v++) {
min = INFINITY; // 当前所知离v顶点的最近距离
for (w = ; w < G.numVertexes; w++) {
if (!final[w] && (*D)[w] < min) {
k = w;
min = (*D)[w];
}
}
final[k] = 1; // 将目前找到的最近的顶点置为1
for (w = ; w < G.numVertexes; w++) {
if (!final[w] && (min + G.arc[k][w] < (*D)[w])) {
// 如果经过当前顶点的路径比已知的路径更短,则更新
(*D)[w] = min + G.arc[k][w];
(*P)[w] = k;
}
}
}
}
```
希望能对你有所帮助!