不是VIP会员,不能显示答案

题目解答

题目:
(最短路径问题)无向连通图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;
 } 
考点:
分析:
解答:
评论:
老师: