程序填空题：Dijkstra Algorithm

The function `Dijkstra` is to find the shortest path from `Vertex S` to every other vertices in a given `Graph`. The distances are stored in `dist[]`, and `path[]` records the paths. The `MGraph` is defined as the following:

```
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv; /* Number of vertices */
int Ne; /* Number of edges */
WeightType G[MaxVertexNum][MaxVertexNum]; /* adjacency matrix */
};
typedef PtrToGNode MGraph;
```


```c++
void Dijkstra( MGraph Graph, int dist[], int path[], Vertex S )
{
int collected[MaxVertexNum];
Vertex V, W;

for ( V=0; VNv; V++ ) {
path[V] = -1;
dist[V] = Graph->G[S][V];
collected[V] = false;
}
dist[S] = 0;
collected[S] = true;

while (1) {
V = FindMinDist( Graph, dist, collected );
if ( V==ERROR ) break;
collected[V] = true;
for( W=0; WNv; W++ )
if ( collected[W]==false && Graph->G[V][W] if ( @@[dist[V]+Graph->G[V][W] < dist[W]](3) ) {
path[W] = @@[V](3);
dist[W] = @@[dist[V]+Graph->G[V][W]](3);
}
}
} /* end while */
}
```






答案：
第1空：dist[V]+Graph->G[V][W] < dist[W]

第2空：V

第3空：dist[V]+Graph->G[V][W]