带权有向图
用c语言回答下述问题假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。
2）实验要求：利用Dijkstra算法求最低的票价
3) 实现提示：
该问题可以归结为一个求带权有向图中顶点间最短路径的问题。
建立以票价为权的有向图，再利用Dijkstra算法求最短路径及其路径长度。 为了实现一个简单的交通指南系统，我们可以使用 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 == 0 && dist <= min)
min = dist, 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);
}
// 利用 Dijkstra 算法求图中顶点间的最短路径
void dijkstra(int graph, int src) {
int dist;// dist 将保留最短路径从 src 到 i 的距离
int sptSet; // sptSet 为 true 代表顶点 i 已经在最短路径集合中，或最短距离已确定
// 初始化所有距离为无穷大，sptSet[] 为 false
for (int i = 0; i < V; i++)
dist = INT_MAX, sptSet = 0;
// 源顶点到自身的距离总是为0
dist = 0;
// 找到所有顶点的最短路径
for (int count = 0; count < V - 1; count++) {
// 选择一个最小距离顶点从未处理过的顶点集合
int u = minDistance(dist, sptSet);
// 标记这个顶点为已处理
sptSet = 1;
// 更新 adj 顶点的 dist 值
for (int v = 0; v < V; v++)
// 更新 dist 只有当它不在 sptSet 中，有一条从 u 到 v 的边，
// 且总的权重路径从 src 到 v 通过 u 是小于当前的 dist
if (!sptSet && graph && dist != INT_MAX && dist + graph < dist)
dist = dist + graph;
}
// 打印构建的距离数组
printSolution(dist, V);
}
int main() {
// 用邻接矩阵表示图
int graph = {{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;
}
页:
[1]