[다익스트라] 다익스트라 알고리즘 1

※다익스트라 알고리즘※

=> 현재까지 알고 있던 최단 경로를 계속해서 갱신해 나가는 알고리즘

※이 문제 어떻게 풀지?※

=> 아직까지는 힙을 사용하지 않음

1. 출발 노드 설정

2. 출발노드를 기준으로 각 노드의 최소 비용을 저장

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택

4. 해당 노드를 거쳐서 특정한 노드로 가능 경우를 고려하여 최소 비용을 갱신

5.위 과정에서 3번 4번 반복

#include<stdio.h>
 
int number = 6;
int INF = 10000000;
 
//전체 그래프를 초기화 합니다.
 
int a[6][6] = {
    {0,2,5,1,INF,INF},
    {2,0,3,2,INF,INF},
    {5,3,0,3,1,5},
    {1,2,3,0,1,INF},
    {INF,INF,1,1,0,2},
    {INF,INF,5,INF,2,0},
};
 
bool v[6]; // 방문한 노드입니다.
int d[6]; // 거리입니다.
 
//가장 최소 거리를 가지는 정점을 반환합니다.
int getSmallIndex(){
    int min = INF;
    int index = 0;
    // 방문되지 않았고 거리 작은거
    for (int i = 0; i < number; i++) {
        if (d[i] < min && !v[i]) {
            min = d[i];
            index = i;
        }
    }
    return index;
}
void dijkstra(int start) {
    for (int i = 0; i < number; i++) {
        d[i] = a[start][i];
    }
 
    v[start] = true;
    for (int i = 0; i < number - 2; i++) {
        int current = getSmallIndex();
        v[current] = true;
        for (int j = 0; j < 6; j++) {
            if (!v[j]) {
                if (d[current] + a[current][j] < d[j]) {
                    d[j] = d[current] + a[current][j];
                }
            }
        }
    }
}
int main() {
    dijkstra(0);
    for (int i = 0; i < number; i++) {
        printf("%d ", d[i]);
    }
    return 0;
}