|
发表于 2023-12-14 18:54:09
|
显示全部楼层
好的,我来给你写一个简单的单源最短路径算法。首先,我们需要明确一下问题的定义:在一个有向图中,给定一个起点,要求找出从起点到其他所有节点的最短路径。
下面是一个基于Dijkstra算法的实现:
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- #define INF 0x3f3f3f3f
- void dijkstra(vector<vector<int>>& graph, int start) {
- int n = graph.size();
- vector<int> dist(n, INF); // 到各个节点的距离,默认为无穷大
- vector<bool> visited(n, false); // 记录节点是否已访问,默认为未访问
- dist[start] = 0; // 起点到自己的距离为0
- // 创建一个最小优先队列,用于按照距离从小到大访问节点
- priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
- pq.push(make_pair(0, start)); // 将起点加入队列
- while (!pq.empty()) {
- int u = pq.top().second;
- pq.pop();
- if (visited[u]) {
- continue; // 该节点已被访问过,直接跳过
- }
- visited[u] = true; // 标记该节点为已访问
- for (int v = 0; v < n; ++v) {
- if (graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) {
- // 如果u到v有边,并且经过u到v比当前距离更短
- dist[v] = dist[u] + graph[u][v]; // 更新距离
- pq.push(make_pair(dist[v], v)); // 将v加入队列
- }
- }
- }
- // 输出最短路径
- cout << "起点到各个节点的最短路径长度:" << endl;
- for (int i = 0; i < n; ++i) {
- cout << start << " 到 " << i << " 的最短路径长度为 " << dist[i] << endl;
- }
- }
- int main() {
- int n = 6; // 节点个数
- vector<vector<int>> graph(n, vector<int>(n, INF)); // 初始化图,默认边权为无穷大
- // 构建图
- graph[0][1] = 2;
- graph[0][2] = 5;
- graph[1][2] = 3;
- graph[1][3] = 7;
- graph[1][4] = 4;
- graph[2][4] = 1;
- graph[2][5] = 3;
- graph[3][4] = 1;
- graph[4][5] = 2;
- int start = 0; // 起点
- dijkstra(graph, start);
- return 0;
- }
复制代码
上述代码中,我们首先定义了一个有向图,用邻接矩阵的方式存储图的边权。然后使用Dijkstra算法计算起点到其他所有节点的最短路径。最后输出起点到各个节点的最短路径长度。
希望这个代码对你有帮助,如果你对Dijkstra算法还有其他疑问,请随时提问!
以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。 |
|