最短路径与最小费用：C++ Dijkstra算法求解自驾游最佳路线

自驾游最佳路线规划：最短路径与最小费用的 Dijkstra 算法求解

问题描述

你准备进行一次自驾游，手上有一份详细的自驾旅游路线图，其中标明了城市之间的高速公路长度以及相应的过路费。你想找到一条从出发地到目的地的最短路径，如果有多条路径长度相同，则选择过路费最少的那条。

解决方案：Dijkstra 算法

这个问题是一个经典的最短路径问题，可以使用 Dijkstra 算法来解决。Dijkstra 算法是一种贪心算法，用于计算加权图中从单个源节点到所有其他节点的最短路径。

C++ 代码实现

以下是使用 C++ 实现 Dijkstra 算法的代码：cpp#include #include #include using namespace std;

struct Road { int city1; int city2; int length; int toll;};

void Dijkstra(int N, int S, int D, const vector& roads) { vector<vector> graph(N, vector(N, numeric_limits::max())); vector<vector> cost(N, vector(N, numeric_limits::max())); vector path(N, -1); vector visited(N, false); vector distance(N, numeric_limits::max()); vector totalCost(N, numeric_limits::max());

for (const auto& road : roads) {        graph[road.city1][road.city2] = road.length;        graph[road.city2][road.city1] = road.length;        cost[road.city1][road.city2] = road.toll;        cost[road.city2][road.city1] = road.toll;    }

distance[S] = 0;    totalCost[S] = 0;

for (int i = 0; i < N; i++) {        int u = -1;        int minDistance = numeric_limits<int>::max();

    for (int j = 0; j < N; j++) {            if (!visited[j] && distance[j] < minDistance) {                u = j;                minDistance = distance[j];            }        }

    if (u == -1) break;

    visited[u] = true;

    for (int v = 0; v < N; v++) {            if (!visited[v] && graph[u][v] != numeric_limits<int>::max()) {                if (distance[u] + graph[u][v] < distance[v]) {                    distance[v] = distance[u] + graph[u][v];                    totalCost[v] = totalCost[u] + cost[u][v];                    path[v] = u;                } else if (distance[u] + graph[u][v] == distance[v] &&                           totalCost[u] + cost[u][v] < totalCost[v]) {                    totalCost[v] = totalCost[u] + cost[u][v];                    path[v] = u;                }            }        }    }

vector<int> shortestPath;    int current = D;

while (current != -1) {        shortestPath.push_back(current);        current = path[current];    }

cout << distance[D] << ' ' << totalCost[D] << endl;

for (int i = shortestPath.size() - 1; i >= 0; i--) {        cout << shortestPath[i];

    if (i > 0) {            cout << ' ';        }    }}

int main() { int N, M, S, D; cin >> N >> M >> S >> D;

vector<Road> roads(M);

for (int i = 0; i < M; i++) {        cin >> roads[i].city1 >> roads[i].city2 >> roads[i].length >> roads[i].toll;    }

Dijkstra(N, S, D, roads);

return 0;}

代码解释

• Road 结构体：用于存储每条高速公路的信息，包括起点城市、终点城市、长度和收费。* Dijkstra 函数：实现 Dijkstra 算法，计算最短路径和最小费用。* main 函数：读取输入数据，调用 Dijkstra 函数，并输出结果。

总结

本文介绍了如何使用 Dijkstra 算法解决最短路径问题，并结合实际案例，通过 C++ 代码实现找到自驾游的最短路径和最小费用。希望对你有所帮助！