程序填空题：Counting the number of shortest paths

The function `NumShortestPaths` is to find the number of shortest paths from `Vertex S` to every other vertices in a given graph (positive weights only). The distances and the numbers of shortest paths are stored in `dist[]` and `num[]`, respectively. The `Graph` is defined as follows:

```c++
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv; /* Number of vertices */
int Ne; /* Number of edges */
int AdjMat[MaxVertexNum][MaxVertexNum]; /* adjacency matrix */
};
typedef PtrToGNode Graph;
```

Please fill in the blanks.

```c++
void NumShortestPaths(Graph G, Vertex S, bool known[], int dist[], int num[])
{
for (int i = 0; i < G->Nv; ++i)
{
known[i] = false;
dist[i] = INFINITY;
num[i] = 0;
}

dist[S] = 0;
@@[num[S] = 1](3);

while (true) {
Vertex V = FindSmallestUnknown(G, known, dist);
if (V == -1) break;

known[V] = true;
for (Vertex W = 0; W < G->Nv; ++W) {
int weight = G->AdjMat[V][W];
if (weight && !known[W]) {
if (dist[V] + weight < dist[W]) {
dist[W] = dist[V] + weight;
num[W] = num[V];
} else if (dist[V] + weight == dist[W]) {
@@[num[W] += num[V]](3);
}
}
}
}
}
```







答案：
第1空：num[S] = 1

第2空：num[W] += num[V]