在本题中,读入一个有向图的带权邻接矩阵(即数组表示),建立有向图并按照迪杰斯特拉算法求出源点至每一个其它顶点的最短路径长度。
时间: 2024-05-07 20:23:05 浏览: 130
Dijkstra算法 邻接矩阵 最短路径
5星 · 资源好评率100%
好的,这个问题可以分成两个部分来解决:第一部分是建立有向图,第二部分是按照迪杰斯特拉算法求出最短路径长度。
先来看第一部分,如何建立有向图。我们可以先定义一个二维数组来表示有向图的带权邻接矩阵,假设这个数组为 `graph`,其中 `graph[i][j]` 表示从顶点 i 到顶点 j 的有向边的权值。如果从顶点 i 到顶点 j 没有有向边,则 `graph[i][j]` 的值为一个很大的数(比如 INT_MAX)。建立有向图的代码如下:
```c++
const int MAXN = 100; // 最大顶点数
const int INF = INT_MAX; // 无穷大
int graph[MAXN][MAXN]; // 带权邻接矩阵
// 读入带权邻接矩阵
void read_graph(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> graph[i][j];
}
}
}
// 输出带权邻接矩阵
void print_graph(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] == INF) {
cout << "INF\t";
} else {
cout << graph[i][j] << "\t";
}
}
cout << endl;
}
}
```
接下来是第二部分,如何按照迪杰斯特拉算法求出最短路径长度。迪杰斯特拉算法的基本思想是从源点开始,每次选择一个距离源点最近的顶点加入到已确定最短路径的顶点集合中,然后更新与该顶点相邻的顶点的距离。具体实现如下:
```c++
// 求最短路径长度
void dijkstra(int n, int s, int *dist) {
bool vis[MAXN]; // 标记是否已确定最短路径
fill(vis, vis + n, false);
fill(dist, dist + n, INF);
dist[s] = 0; // 源点到自身的距离为 0
for (int i = 0; i < n; i++) {
int u = -1; // 找到距离源点最近的未确定最短路径的顶点
for (int j = 0; j < n; j++) {
if (!vis[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
vis[u] = true; // 把 u 加入到已确定最短路径的顶点集合中
// 更新与 u 相邻的顶点的距离
for (int v = 0; v < n; v++) {
if (!vis[v] && graph[u][v] != INF) {
dist[v] = min(dist[v], dist[u] + graph[u][v]);
}
}
}
}
```
最后,我们可以在 `main` 函数中调用上述两个函数来完成整个程序。完整代码如下:
阅读全文