(最短路径问题)无向连通图G 有n 个结点,依次编号为0,1,2,...,(n-1)。用邻接矩阵的形式给出每条边的边长,要求输出以结点0 为起点出发,到各结点的最短路径长度。
使用Dijkstra 算法解决该问题:利用dist 数组记录当前各结点与起点的已找到的最短路径长度;每次从未扩展的结点中选取dist 值最小的结点v 进行扩展,更新与v 相邻的结点的dist 值;不断进行上述操作直至所有结点均被扩展,此时dist 数据中记录的值即为各结点与起点的最短路径长度。(第五空2 分,其余3 分)
#include <iostream>
using namespace std;
const int MAXV = 100;
int n, i, j, v;
int w[MAXV][MAXV];
//邻接矩阵,记录边长
// 其中w[i][j]为连接结点i 和结点j 的无向边长度,若无边则为-1
int dist[MAXV];
int used[MAXV];
//记录结点是否已扩展(0:未扩展;1:已扩展)
int main() {
cin >> n;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
cin >> w[i][j];
dist[0] = 0;
for (i = 1; i < n; i++)
dist[i] = -1;
for (i = 0; i < n; i++)
used[i] = 0;
while (true) {
v=-1 ;
for (i = 0; i < n; i++)
if (used[i] != 1 && dist[i] != -1 && (v == -1 || dist[i]<=dist[v] ))
v=i ;
if (v == -1)
break;
used[v]=1 ;
for (i = 0; i < n; i++)
if (w[v][i] != -1 && (dist[i] == -1 || dist[v]+w[v][i]<dist[i] ))
dist[i] = dist[v] + w[v][i];
}
for (i = 0; i < n; i++)
cout << dist[i] << endl;
return 0;
}