Write a program to find the weighted shortest distances from any vertex to a given source vertex in a digraph. If there is more than one minimum path from v to w, a path with the fewest number of edges is chosen. It is guaranteed that all the weights are positive and such a path is unique for any vertex. Format of functions: void ShortestDist( MGraph Graph, int dist[], int path[], Vertex S ); where MGraph is defined as the following: typedef struct GNode *PtrToGNode; struct GNode{ int Nv; int Ne; WeightType G[MaxVertexNum][MaxVertexNum]; }; typedef PtrToGNode MGraph; The shortest distance from V to the source S is supposed to be stored in dist[V]. If V cannot be reached from S, store -1 instead. If W is the vertex being visited right before V along the shortest path from S to V, then path[V]=W. If V cannot be reached from S, path[V]=-1, and we have path[S]=-1. Sample program of judge: #include #include typedef enum {false, true} bool; #define INFINITY 1000000 #define MaxVertexNum 10 /* maximum number of vertices */ typedef int Vertex; /* vertices are numbered from 0 to MaxVertexNum-1 */ typedef int WeightType; typedef struct GNode *PtrToGNode; struct GNode{ int Nv; int Ne; WeightType G[MaxVertexNum][MaxVertexNum]; }; typedef PtrToGNode MGraph; MGraph ReadG(); /* details omitted */ void ShortestDist( MGraph Graph, int dist[], int path[], Vertex S ); int main() { int dist[MaxVertexNum], path[MaxVertexNum]; Vertex S, V; MGraph G = ReadG(); scanf(

where MGraph is defined as the following: typedef struct GNode *PtrToGNode; struct GNode{ int Nv; int Ne; WeightType G[MaxVertexNum][MaxVertexNum]; }; typedef PtrToGNode MGraph; The shortest distance from V to the source S is supposed to be stored in dist[V]. If V cannot be reached from S, store -1 instead. If W is the vertex being visited right before V along the shortest path from S to V, then path[V]=W. If V cannot be reached from S, path[V]=-1, and we have path[S]=-1.

Return the shortest path of any vertex to the given source vertex in a diagraph

166