单源最短路径efuoj
时间: 2023-11-01 13:14:00 浏览: 41
单源最短路径算法有多种,包括Dijkstra算法、Bellman-Ford算法、SPFA算法等。在EFOJ上,可以通过以下步骤实现Dijkstra算法求解单源最短路径:
1. 定义一个数组dist,用于存储起点到每个节点的最短距离,初始时将起点的dist值设为0,其他节点的dist值设为无穷大。
2. 定义一个优先队列,用于存储待处理的节点。将起点加入队列。
3. 对队列中的节点进行处理,每次取出dist值最小的节点,并更新其相邻节点的dist值。具体操作如下:
- 对于当前节点u,遍历其所有相邻节点v,如果从起点到v的距离比起点到u再到v的距离更短,更新v的dist值为新的距离,并将v加入队列中。
4. 重复步骤3,直到队列为空。
下面是一个示例代码实现:
```c++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1005;
vector<pair<int, int>> adj[MAXN];
int dist[MAXN];
bool vis[MAXN];
void dijkstra(int s) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(0, s));
dist[s] = 0;
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i].first;
int w = adj[u][i].second;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push(make_pair(dist[v], v));
}
}
}
}
int main() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back(make_pair(v, w));
}
memset(dist, INF, sizeof(dist));
dijkstra(s);
for (int i = 1; i <= n; i++) {
cout << dist[i] << " ";
}
cout << endl;
return 0;
}
```
其中,adj数组存储图的邻接表,dist数组存储每个节点的最短距离,vis数组用于记录节点是否已经处理过。在上述代码中,我们使用了STL中的优先队列来实现Dijkstra算法,可以看到代码非常简洁。