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

 

 

 

1. 비용을 정렬한다.

2. 비용이 작은 노드부터 방문한다.

3. 시작점으로부터의 비용을 갱신한다.

 

 

 

 

C언어 코드

#include <stdio.h>
#include <limits.h>

#define TRUE    1
#define FALSE   0
#define MAX_VERTICES    100     /* 노드의 수 */
#define INF     9999        /* 무한 값(연결이 없는 경우) */

int distance[MAX_VERTICES]; /* 시작노드로부터의 최단경로 거리 */
int previous[MAX_VERTICES]; /* 경유 노드  :  이 배열의 값을 어떻게 설정할 것인가?가 이 숙제의 문제*/
int found[MAX_VERTICES];    /* 방문한 노드 표시 */

typedef struct GraphType {
    int n;                  // 정점의 개수
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;

// 그래프 초기화
void graph_init(GraphType *g)
{
    int r,c;
    g->n = 0;
    for (r = 0; r < MAX_VERTICES; r++)
    for (c = 0; c < MAX_VERTICES; c++)
    g->adj_mat[r][c] = INF;
    
    for (r = 0; r < MAX_VERTICES; r++) // pak 추가
    g->adj_mat[r][r] = 0;
}

int choose(int distance[], int n, int found[])
{
    int i, min, minpos;
    min = INT_MAX;
    minpos = -1;
    for (i=0; i < n; i++)
    if (distance[i] < min && ! found[i]) {
        min = distance[i];
        minpos=i;
    }
    return minpos;
}


void read_graph_to_adj_mat(GraphType *g)
{
    int n, u, v;
    scanf("%d", &n);
    g->n = n;
    scanf("%d", &u);
    while (u != -1)
    {
        scanf("%d", &v);
        scanf("%d", &g->adj_mat[u][v]);
        g->adj_mat[v][u] = g->adj_mat[u][v];
        
        scanf("%d", &u);
    }
}
void print_path(int start, int end)
{
    int u = end ;
    if(start == end) {
        printf("%d", start);
        return;
    }
    else {
        print_path(start, previous[u]);
        printf("->%d", u);
    }
}
void shortest_path(GraphType *g, int start, int e, int except) /* 시작노드 */
{
    int i, u, w;
    for(i=0; i<g->n; i++)   /* 초기화 */
    {
        distance[i] = g->adj_mat[start][i];
        found[i] = FALSE;
        previous[i] =start;
    }
    
    found[start] = TRUE;    /* 시작노드 방문 표시 */
    distance[start] = 0;
    
    for(i = 0; i < (g->n)-1; i++) {
        u = choose(distance, g->n, found);
        found[u] = TRUE;
        if(u == except) continue;
        if(u == e) {
            print_path(start, u);
            printf("(%d)\n", distance[u]);
        }
        for(w=0; w<g->n; w++) { // distance[] 재조정
            if(!found[w])
                if( distance[u] + g->adj_mat[u][w] < distance[w] ) {
                    distance[w] = distance[u] + g->adj_mat[u][w];
                    previous[w] = u;
                }
        }
    }
}

int main()
{
    GraphType g;        // 입력 그래프
    int sIndex, dIndex, eIndex;
    graph_init(&g);;
    
    read_graph_to_adj_mat(&g);
    
    //printf("시작점:");
    scanf("%d", &sIndex);
    //printf("도착점:");
    scanf("%d", &dIndex);
    
    //printf("제외점:");
    scanf("%d", &eIndex);
    //shortest_path(&g, sIndex, dIndex);
    shortest_path(&g, sIndex, dIndex, eIndex);
}

 

 

 

 

 

파이썬의 우선순위 큐를 사용해보면 좋을 것 같다.

www.daleseo.com/python-priority-queue/

파이썬의 우선순위 큐(PriorityQueue) 사용법

www.daleseo.com/python-heapq/

[파이썬] heapq 모듈 사용법