用C++完整代码解决:有一个含n个顶点(顶点编号为0~n-1)的带权图,用邻接矩阵数组A表示,采用分枝限界法求从起点s到目标点t的最短路径长度,以及具有最短路径长度的路径条数
时间: 2023-06-27 09:04:54 浏览: 147
求带权图最短路径的代码
5星 · 资源好评率100%
以下是C++代码实现:
```
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 100; // 最大顶点数
const int INF = 0x7FFFFFFF; // 无穷大
int n, s, t; // n表示顶点数,s表示起点,t表示终点
int A[MAXN][MAXN]; // 邻接矩阵数组
int dist[MAXN]; // 存储当前最短路径长度
int num[MAXN]; // 存储当前最短路径条数
bool vis[MAXN]; // 标记是否已访问
struct Node {
int u, d;
bool operator < (const Node& rhs) const {
return d > rhs.d; // 用于小根堆
}
};
void dijkstra() {
priority_queue<Node> q;
memset(vis, 0, sizeof(vis));
memset(num, 0, sizeof(num));
for (int i = 0; i < n; i++) {
dist[i] = INF;
}
dist[s] = 0;
num[s] = 1;
q.push({s, 0});
while (!q.empty()) {
int u = q.top().u;
q.pop();
if (vis[u]) continue;
vis[u] = true;
for (int v = 0; v < n; v++) {
if (A[u][v] != INF && !vis[v]) {
if (dist[u] + A[u][v] < dist[v]) {
dist[v] = dist[u] + A[u][v];
num[v] = num[u];
q.push({v, dist[v]});
} else if (dist[u] + A[u][v] == dist[v]) {
num[v] += num[u];
}
}
}
}
}
int main() {
cin >> n >> s >> t;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> A[i][j];
if (A[i][j] == -1) {
A[i][j] = INF;
}
}
}
dijkstra();
cout << dist[t] << endl;
cout << num[t] << endl;
return 0;
}
```
其中,dijkstra函数实现了Dijkstra算法,用小根堆优化,求出起点到各个顶点的最短路径长度和最短路径条数。在主函数中,先读入图的邻接矩阵表示,然后调用dijkstra函数求解,最后输出结果。
阅读全文