单元最短路径的Dijkstra算法
时间: 2023-12-31 17:21:59 浏览: 38
Dijkstra算法是一种用于计算图中单源最短路径的贪心算法。它的基本思想是从起点开始,逐步扩展到距离起点更远的节点,直到到达终点为止。在这个过程中,我们维护一个距离起点的最短距离数组和一个已经确定最短路径的节点集合。每次从未确定最短路径的节点中选择距离起点最近的节点,然后更新该节点的邻居节点的最短距离。重复这个过程,直到到达终点或者所有未确定最短路径的节点都已经被处理。
以下是Dijkstra算法的C++实现代码:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
const int MAXN = 100; // 最大节点数
vector<pair<int, int>> adj[MAXN]; // 邻接表表示图
int dist[MAXN]; // 距离起点的最短距离
bool visited[MAXN]; // 是否已经确定最短路径
void dijkstra(int start) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(0, start));
dist[start] = 0;
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (visited[u]) {
continue;
}
visited[u] = true;
for (auto v : adj[u]) {
int w = v.first;
int weight = v.second;
if (dist[u] + weight < dist[w]) {
dist[w] = dist[u] + weight;
pq.push(make_pair(dist[w], w));
}
}
}
}
int main() {
int n, m, start, end;
cin >> n >> m >> start >> end;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
fill(dist, dist + MAXN, INT_MAX);
dijkstra(start);
cout << dist[end] << endl;
return 0;
}
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)