数据结构输出最短路径代码
时间: 2024-05-31 13:06:28 浏览: 78
数据结构中用于输出最短路径的常用算法有Dijkstra算法和Bellman-Ford算法。其中,Dijkstra算法适用于有向图中没有负边权的情况,而Bellman-Ford算法则可以处理有向图中存在负边权的情况。
以下是使用Dijkstra算法输出最短路径的示例代码:
```
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f; // 定义一个无穷大的值
struct Edge {
int to;
int cost;
};
typedef pair<int, int> P; // first表示到起点的距离,second表示顶点编号
vector<Edge> G[1000]; // 图的邻接表表示
int d[1000]; // 存储起点到各个顶点的最短距离
void dijkstra(int s) { // s为起点编号
priority_queue<P, vector<P>, greater<P>> que;
fill(d, d + 1000, INF);
d[s] = 0;
que.push(P(0, s));
while (!que.empty()) {
P p = que.top();
que.pop();
int v = p.second;
if (d[v] < p.first) {
continue;
}
for (int i = 0; i < G[v].size(); i++) {
Edge e = G[v][i];
if (d[e.to] > d[v] + e.cost) {
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to], e.to));
}
}
}
}
int main() {
int V, E, r;
cin >> V >> E >> r;
for (int i = 0; i < E; i++) {
int s, t, d;
cin >> s >> t >> d;
G[s].push_back((Edge){t, d});
}
dijkstra(r);
for (int i = 0; i < V; i++) {
if (d[i] == INF) {
cout << "INF" << endl;
} else {
cout << d[i] << endl;
}
}
return 0;
}
```