|
发表于 2023-12-14 14:31:03
|
显示全部楼层
为了实现一个简单的交通指南系统,我们可以使用 Dijkstra 算法来找到带权有向图中两个顶点间的最短路径。
一点参考实现:
- #include <stdio.h>
- #include <limits.h> // 用于 INT_MAX
- #define V 9 // 图中顶点的数量
- // 用于找出距离集合中最小距离顶点的下标,sptSet[] 为 true 的顶点将不被考虑
- int minDistance(int dist[], int sptSet[]) {
- int min = INT_MAX, min_index;
- for (int v = 0; v < V; v++)
- if (sptSet[v] == 0 && dist[v] <= min)
- min = dist[v], min_index = v;
- return min_index;
- }
- // 打印最短路径的距离
- void printSolution(int dist[], int n) {
- printf("Vertex Distance from Source\n");
- for (int i = 0; i < V; i++)
- printf("%d \t %d\n", i, dist[i]);
- }
- // 利用 Dijkstra 算法求图中顶点间的最短路径
- void dijkstra(int graph[V][V], int src) {
- int dist[V]; // dist[i] 将保留最短路径从 src 到 i 的距离
- int sptSet[V]; // sptSet[i] 为 true 代表顶点 i 已经在最短路径集合中,或最短距离已确定
- // 初始化所有距离为无穷大,sptSet[] 为 false
- for (int i = 0; i < V; i++)
- dist[i] = INT_MAX, sptSet[i] = 0;
- // 源顶点到自身的距离总是为0
- dist[src] = 0;
- // 找到所有顶点的最短路径
- for (int count = 0; count < V - 1; count++) {
- // 选择一个最小距离顶点从未处理过的顶点集合
- int u = minDistance(dist, sptSet);
- // 标记这个顶点为已处理
- sptSet[u] = 1;
- // 更新 adj 顶点的 dist 值
- for (int v = 0; v < V; v++)
- // 更新 dist[v] 只有当它不在 sptSet 中,有一条从 u 到 v 的边,
- // 且总的权重路径从 src 到 v 通过 u 是小于当前的 dist[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, V);
- }
- 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;
- }
复制代码 |
|