4-2 Shortest Path [4]
3214 단어 데이터 구조
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("%d", &S);
ShortestDist( G, dist, path, S );
for ( V=0; VNv; V++ )
printf("%d ", dist[V]);
printf("
");
for ( V=0; VNv; V++ )
printf("%d ", path[V]);
printf("
");
return 0;
}
/* Your function will be put here */
Sample Input (for the graph shown in the figure):
8 11
0 4 5
0 7 10
1 7 40
3 0 40
3 1 20
3 2 100
3 7 70
4 7 5
6 2 1
7 5 3
7 2 50
3
Sample Output:
40 20 100 0 45 53 -1 50
3 3 3 -1 0 7 -1 0
result:
void ShortestDist( MGraph Graph, int dist[], int path[], Vertex S )
{
Vertex know[MaxVertexNum];
Vertex i,j;
Vertex min;
for(i=0;iNv;i++)
{
know[i]=0;
dist[i]=INFINITY;
path[i]=-1;
}
dist[S]=0;
while(1)
{
j=-1;
min=INFINITY;
for(i=0;iNv;i++)
{
if(know[i]==0&&dist[i]Nv;i++)
{
if(know[i]==0)
{
if(dist[j]+Graph->G[j][i]G[j][i];
path[i]=j;
}
}
}
}
for(i=0;iNv;i++)
{
if(dist[i]==INFINITY)
{
dist[i]=-1;
}
}
path[S]=-1;
dist[S]=0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.