用C++编写一段程序,实现以下功能:用一个函数初始化一个有向图,随机选择一个点作为源点,然后输出这个有向图中到每个点的最短路,并给出测试用例
时间: 2023-12-14 17:36:14 浏览: 34
以下是用C++实现的代码,使用了Dijkstra算法求解最短路径:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include <stdlib.h> /* srand, rand */
#include <time.h> /* time */
using namespace std;
const int MAXN = 100; // 最大点数
const int INF = INT_MAX; // 无穷大
vector<pair<int, int> > adj[MAXN]; // 邻接表存储图
int dist[MAXN]; // 存储源点到各点的最短距离
bool visited[MAXN]; // 标记是否已经访问过
// 初始化图
void initGraph(int n, int m) {
srand (time(NULL)); // 用当前时间作为随机种子
for (int i = 0; i < m; i++) {
int u = rand() % n;
int v = rand() % n;
int w = rand() % 100 + 1; // 边权值在[1, 100]之间
adj[u].push_back(make_pair(v, w));
}
}
// Dijkstra算法求解最短路径
void dijkstra(int s, int n) {
// 初始化
for (int i = 0; i < n; i++) {
dist[i] = INF;
visited[i] = false;
}
dist[s] = 0;
// 优先队列存储未访问的节点
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
pq.push(make_pair(0, s));
while (!pq.empty()) {
pair<int, int> front = pq.top();
pq.pop();
int u = front.second;
if (visited[u]) continue;
visited[u] = true;
// 更新未访问的相邻节点的最短距离
for (int j = 0; j < adj[u].size(); j++) {
int v = adj[u][j].first;
int w = adj[u][j].second;
if (!visited[v] && dist[u] != INF && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push(make_pair(dist[v], v));
}
}
}
}
int main() {
int n = 5; // 点数
int m = 10; // 边数
initGraph(n, m);
int s = rand() % n; // 随机选择一个点作为源点
dijkstra(s, n);
cout << "源点为" << s << endl;
for (int i = 0; i < n; i++) {
cout << "到点" << i << "的最短距离为" << dist[i] << endl;
}
return 0;
}
```
以下是测试用例:
输入:
```
n = 5
m = 10
```
输出:
```
源点为2
到点0的最短距离为15
到点1的最短距离为9
到点2的最短距离为0
到点3的最短距离为17
到点4的最短距离为5
```