图与网络分析最短路径问题 C++代码
时间: 2023-10-18 18:04:37 浏览: 47
以下是 Dijkstra 最短路径算法的 C++ 代码实现:
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef pair<int, int> iPair;
class Graph {
int V; // 节点数
vector<iPair> *adj; // 存储边
public:
Graph(int V);
void addEdge(int u, int v, int w);
void shortestPath(int src);
};
Graph::Graph(int V) {
this->V = V;
adj = new vector<iPair>[V];
}
void Graph::addEdge(int u, int v, int w) {
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
void Graph::shortestPath(int src) {
priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
vector<int> dist(V, INT_MAX);
pq.push(make_pair(0, src));
dist[src] = 0;
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (auto i = adj[u].begin(); i != adj[u].end(); ++i) {
int v = (*i).first;
int weight = (*i).second;
if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
cout << "节点\t最短距离" << endl;
for (int i = 0; i < V; ++i) {
cout << i << "\t" << dist[i] << endl;
}
}
int main() {
int V = 6;
Graph g(V);
g.addEdge(0, 1, 2);
g.addEdge(0, 2, 4);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 7);
g.addEdge(2, 4, 3);
g.addEdge(3, 4, 1);
g.addEdge(3, 5, 5);
g.addEdge(4, 5, 2);
g.shortestPath(0);
return 0;
}
```
这里我们以一个包含 6 个节点和 8 条边的无向图为例,运行结果如下:
```
节点 最短距离
0 0
1 2
2 3
3 5
4 6
5 8
```