(1)编写用邻接矩阵表示有向带权网时,图的基本操作的实现函数,主要包括: ①初始化邻接矩阵表示的有向带权图 ②建立邻接矩阵表示的有向带权图 (即通过输入图的每条边建立图的邻接矩阵) ③出邻接矩阵表示的有向带权图(即输出图的每条边)。 ④编写求最短路径的DijKstra算法函数 void Dijkstra( adjmatrix GA, int dist[], edgenode *path[], int i, int n) ,该算法求从顶点i到其余顶点的最短路径与最短路径长度,并分别存于数组 path 和 dist 中。(可选) ⑤编写打印输出从源点到每个顶点的最短路径及长度的函数 void PrintPath(int dist[], edgenode *path[], int n)。(可选) 同时建立一个验证操作实现的主函数main()进行测试。
时间: 2024-02-16 22:00:49 浏览: 35
好的,我明白了您的问题。以下是对应的函数实现:
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 100;
const int INF = 1e9;
typedef struct {
int from;
int to;
int weight;
} Edge;
typedef struct {
int n; // 顶点数
int m; // 边数
int graph[MAXN][MAXN]; // 邻接矩阵
} AdjMatrix;
void init(AdjMatrix& g, int n) {
g.n = n;
g.m = 0;
memset(g.graph, 0, sizeof(g.graph));
}
void add_edge(AdjMatrix& g, int u, int v, int w) {
g.graph[u][v] = w;
g.m++;
}
void build(AdjMatrix& g) {
int u, v, w;
while (scanf("%d%d%d", &u, &v, &w) != EOF) {
add_edge(g, u, v, w);
}
}
void print(AdjMatrix& g) {
for (int i = 0; i < g.n; i++) {
for (int j = 0; j < g.n; j++) {
if (g.graph[i][j] != 0) {
printf("(%d, %d, %d) ", i, j, g.graph[i][j]);
}
}
printf("\n");
}
}
void Dijkstra(AdjMatrix& g, int dist[], Edge* path[], int s) {
bool vis[MAXN] = {false};
for (int i = 0; i < g.n; i++) {
dist[i] = INF;
}
dist[s] = 0;
for (int i = 0; i < g.n; i++) {
int x, min_dist = INF;
for (int j = 0; j < g.n; j++) {
if (vis[j] == false && dist[j] < min_dist) {
x = j;
min_dist = dist[j];
}
}
vis[x] = true;
for (int y = 0; y < g.n; y++) {
if (g.graph[x][y] != 0) {
int d = dist[x] + g.graph[x][y];
if (d < dist[y]) {
dist[y] = d;
path[y]->from = x;
path[y]->to = y;
path[y]->weight = g.graph[x][y];
}
}
}
}
}
void print_path(AdjMatrix& g, int dist[], Edge* path[], int s) {
for (int i = 0; i < g.n; i++) {
printf("shortest path from %d to %d: ", s, i);
if (dist[i] == INF) {
printf("no path\n");
} else {
printf("%d", s);
for (Edge* e = path[i]; e->from != s; e = path[e->from]) {
printf("->%d", e->from);
}
printf("->%d, shortest distance: %d\n", i, dist[i]);
}
}
}
int main() {
AdjMatrix g;
init(g, 6);
add_edge(g, 0, 1, 10);
add_edge(g, 0, 4, 15);
add_edge(g, 1, 2, 20);
add_edge(g, 1, 3, 25);
add_edge(g, 2, 3, 30);
add_edge(g, 3, 5, 5);
add_edge(g, 4, 5, 20);
print(g);
int dist[MAXN];
Edge* path[MAXN];
for (int i = 0; i < g.n; i++) {
path[i] = new Edge;
}
Dijkstra(g, dist, path, 0);
print_path(g, dist, path, 0);
return 0;
}
```
这个代码实现了有向带权图的邻接矩阵表示、Dijkstra算法求最短路径和打印最短路径的函数,主函数中还提供了一个简单的测试用例。当然,你也可以自己输入测试数据进行验证。