[작업 압축 파일] Dijkstra 알고리즘 연습

무모 한 소년 으로서 이번 숙제 를 마 치 는 데 우여곡절 을 겪 었 다.
목 표 는 함수 로 이 루어 지 는 것 입 니 다. 그림 에서 모든 점 에서 소스 까지 의 가중 최 단 경 로 를 찾 아 총 길이 (변 의 가중치 와) 와 항목 수 를 기록 하 는 것 입 니 다.연결 되 지 않 으 면 총 길 이 는 - 1 과 개수 0 이다.
dist 는 총 길 이 를 기록 하고 count 기록 은 이러한 경 로 를 몇 개 찾 았 습 니 다.
Dijkstra 알고리즘 을 사용 하면 아주 간단 합 니 다. 하지만 제 가 너무 급 하고 경박 해서 D 알고리즘 을 철저하게 파악 하지 못 하고 바로 시작 해서 먼 길 을 돌 았 습 니 다.
하지만 중요 한 것 도 배 웠 습 니 다.
1. 코드 를 쓰기 전에 알고리즘 을 잘 알 아야 합 니 다.
2. 학습 데이터 구 조 는 수업 을 듣 지 않 으 면 되 고 수업 시간 에 공 을 들 여 연구 해 야 한다.
3. 자신의 알고리즘 을 고 치 는 것 이 어렵 다 는 것 을 알 았 을 때 생각 을 바 꾸 세 요.
4. 같은 코드 를 쓰 고 두 시간 이 넘 으 면 다른 일 을 하고 돌아 오 면 바로 뒤 집 고 다시 쓸 수 있다.
[지식 점 복습]: 행렬 로 방향 도 를 나타 내 고 행 은 출발 의 결점 을 나타 내 며 들 어 가 는 노드 를 나타 낸다.
[오류 요약]:
Queue 로 Dijkstra 알고리즘 을 구현 하려 면 최소 로 쌓 아야 합 니 다.
두 번 의 D 알고리즘 (인터넷 코드 를 참고 하여 한 번 으로 합 칠 수 있 음) 과 한 번 의 D 알고리즘 중 디 테 일 한 오류 (if 구문 괄호 가 모두 포함 되 지 않 음) 가 많 지만 가장 중요 한 문 제 는 Graph - > G [V] [W] 가 부족 하 다 는 것 입 니 다! = INFINITY
그러나 제목 은 이런 이 야 기 를 한 적 이 없다.
아래 에 마지막 코드 를 올 려 주세요.

void ShortestDist(MGraph Graph, int dist[], int count[], Vertex S){
    bool isVisit[MaxVertexNum];
    int i, minDis,V, W, tmpDis;
    
    for (i = 0; i < Graph->Nv; i++){
        dist[i] = -1;
        
        count[i] = 0;
        isVisit[i] = false;
    }
    dist[S] = 0;
    count[S] = 1;
    
    while (1){
        minDis = INFINITY;
        
        for (i = 0; i < Graph->Nv; i++){
            if (!isVisit[i] && dist[i] < minDis && dist[i] != -1){
                V = i;
                minDis = dist[V];
            }
        }
        if (minDis == INFINITY) break;
        isVisit[V] = true;
        
        for (W = 0; W < Graph->Nv; W++){
            tmpDis = dist[V] + Graph->G[V][W];
            if(isVisit[W] == false && Graph->G[V][W] >= 0 && Graph->G[V][W] != INFINITY){
                if( (dist[V] + Graph->G[V][W] < dist[W]||dist[W] == -1)){
                    dist[W] = tmpDis;
                    count[W] = count[V];
                }
                else if (dist[V] + Graph->G[V][W] == dist[W]){
                    count[W] += count[V];
                    
                }
            }
        }
    }
    
    
    
}

제목
4-1 Shortest Path [3]   (25 분)
Write a program to not only find the weighted shortest distances, but also count the number of different minimum paths from any vertex to a given source vertex in a digraph. It is guaranteed that all the weights are positive.
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