（最短路径问题）无向连通图G有n个结点，依次编

（最短路径问题）无向连通图G有n个结点，依次编号为0,1,2,...,(n-1)。用邻接矩阵的形式给出每条边的边长，要求输出以结点0为起点出发，到各结点的最短路径长度。

使用Dijkstra算法解决该问题：利用dist数组记录当前各结点与起点的已找到的最短路径长度；每次从未扩展的结点中选取dist值最小的结点v进行扩展，更新与v相邻的结点的dist值；不断进行上述操作直至所有结点均被扩展，此时dist数据中记录的值即为各结点与起点的最短路径长度。（第五空 2 分，其余 3 分）

#include

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() {

\tcin >> n;

\tfor (i = 0; i < n; i )

\t\tfor (j = 0; j < n; j )

\t\t\tcin >> w[i][j];

\tdist[0] = 0;

\tfor (i = 1; i < n; i )

\t\tdist[i] = -1;

\tfor (i = 0; i < n; i )

\t\tused[i] = 0;

\twhile (true) {

(1) ;

\t\tfor (i = 0; i < n; i )

\t\t\tif (used[i] != 1 && dist[i] != -1 && (v == -1 || (2) ))

\t\t (3) ;

\t\tif (v == -1)

\t\t\tbreak;

\t (4) ;

\t\tfor (i = 0; i < n; i )

\t\t\tif (w[v][i] != -1 && (dist[i] == -1 || (5) ))

\t\t\t\tdist[i] = dist[v] w[v][i];

\t}

\tfor (i = 0; i < n; i )

\t\tcout << dist[i] << endl;

\treturn 0;

}