Shortest Path [3]
3748 단어 데이터 구조
Format of functions:
void ShortestDist( MGraph Graph, int dist[], int count[], 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. The number of different minimum paths from V
to the source S
is supposed to be stored in count[V]
and count[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 count[], Vertex S );
int main()
{
int dist[MaxVertexNum], count[MaxVertexNum];
Vertex S, V;
MGraph G = ReadG();
scanf("%d", &S);
ShortestDist( G, dist, count, S );
for ( V=0; VNv; V++ )
printf("%d ", dist[V]);
printf("
");
for ( V=0; VNv; V++ )
printf("%d ", count[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 30
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
1 1 4 1 1 3 0 3
Result:
void ShortestDist( MGraph Graph, int dist[], int count[], Vertex S )
{
Vertex know[MaxVertexNum];
Vertex i,j;
Vertex min;
Vertex dist2[MaxVertexNum];
for(i=0;iNv;i++)
{
know[i]=0;
dist[i]=INFINITY;
dist2[i]=INFINITY;
count[i]=0;
}
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];
}
}
}
}
for(i=0;iNv;i++)
{
know[i]=0;
}
dist2[S]=0;
count[S]=1;
while(1)
{
j=-1;
min=INFINITY;
for(i=0;iNv;i++)
{
if(know[i]==0&&dist2[i]Nv;i++)
{
if(know[i]==0)
{
if(dist2[j]+Graph->G[j][i]G[j][i];
count[i]=count[j];
}
else if(dist[i]!=INFINITY&&dist2[j]+Graph->G[j][i]==dist[i])
count[i]=count[j]+count[i];
}
}
}
for(i=0;iNv;i++)
{
if(dist[i]==INFINITY)
{
dist[i]=-1;
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.