[알고리즘] ep7+) 다익스트라와 벨만-포드 알고리즘 구현

주의: 그래프 알고리즘 구현 시, 그래프의 인접 정보(즉, 부착 간선리스트 또는 인접행렬) 없이도 수행 가능한 문제라고 판단되면 간선리스트 구조로 그래프를 간편하게 구현할 것을 우선적으로 고려하라. 그렇지 않고, 인접 정보가 있어야 수행한다고 판단되면 인접리스트 구조 또는 인접행렬 구조 중에 해당 문제 해결에 효율성 면에서 유리하다고 판단되는 것을 선택하여 구현하라.

 

 

문제1) 무방향 양의 가중그래프 -> 다익스트라 알고리즘

무방향 양의 가중그래프(undirected weighted graph) G와 출발정점이 주어지면, 출발정점에서 다른 모든 정점으로 가는 최단거리를 구하는 프로그램을 작성하라.

 

입력 그래프의 성질:
◦ n(1 ≤ n ≤ 100)개의 정점과 m(1 ≤ m ≤ 1,000)개의 간선으로 구성.
◦ 정점은 1 ~ n 사이의 정수로 번호가 매겨져 있고, 정점의 번호는 모두 다름.

◦ 모든 간선은 무방향간선이다.

 

• 입력

-  첫 줄에 정점의 개수 n, 간선의 개수 m, 출발정점 번호 s가 주어진다.

-  이후 m개의 줄에 한 줄에 하나씩 간선의 정보(간선의 양 끝 정점 번호, 무게)가 주어진다. 최대로 가능한 가중치는 20을 넘지 않는다고 가정한다. 간선은 임의의 순서로 입력되고, 중복 입력되는 간선은 없다(무방향간선이므로 간선 (u, v)와 (v, u)는 동일한 간선으로 취급).

 

• 출력

- 출발정점 s에서 다른 모든 정점으로의 최단거리를 출력한다. 한 줄에 한 정점과 그 정점까지의 거리를 출력하되, 출력하는 순서는 정점의 번호의 오름차순으로 출력한다. 도달할 수 없는 정점은 출력하지 않는다.

 

 

 

 

 

 

 

(전체코드) - 우선순위 큐 사용 X - O(n^2)

// 무방향 양의 가중그래프
// 다익스트라 알고리즘 
// 우선순위 큐 사용 X - O(n^2)
#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 100

typedef struct EDGE {
    int vertex;
    int w;
} EDGE;

// 인접 리스트를 나타내는 구조체
typedef struct EDGELIST {
    EDGE edges[MAX_NODES];
    int edgeSize;
} EDGELIST;

EDGELIST adjList[MAX_NODES]; // 인접리스트 배열
int distance[MAX_NODES]; // 최단 거리 배열
int visited[MAX_NODES]; // 방문한 노드 배열

void initGraph(int n);
void addEdge(int curV, int v, int w);
int extractMin(int n);
void Dijkstra(int start, int n);

int main() {
    int n, m, s;
    int u, v, w;

    scanf("%d %d %d", &n, &m, &s);
    initGraph(n);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &u, &v, &w);
        addEdge(u - 1, v - 1, w);
    }

    Dijkstra(s - 1, n);
    for (int i = 0; i < n; i++) {
        if (i != s - 1 && distance[i] != 2147483647) {
			// 시작 정점이 아니고 도달 가능한 정점인 경우 출력
            printf("%d %d\n", i + 1, distance[i]);
        }
    }
    return 0;
}

void initGraph(int n) {
    for (int i = 0; i < n; i++) {
        adjList[i].edgeSize = 0;
        distance[i] = 2147483647;
        visited[i] = 0;
    }
}

void addEdge(int u, int v, int w) {
    // 정점 u에 간선 추가
    adjList[u].edges[adjList[u].edgeSize].vertex = v;
    adjList[u].edges[adjList[u].edgeSize].w = w;
    adjList[u].edgeSize++;
    // 정점 v에 간선 추가 (무방향 그래프이므로 양쪽에 추가)
    adjList[v].edges[adjList[v].edgeSize].vertex = u;
    adjList[v].edges[adjList[v].edgeSize].w = w;
    adjList[v].edgeSize++;
}

// 방문하지 않은 정점 중 최소 거리를 가진 정점을 추출하는 함수
int extractMin(int n) {
    int minDist = 2147483647;
    int minIdx = -1;
    for (int i = 0; i < n; i++) {
        if (!visited[i] && distance[i] < minDist) {
            minDist = distance[i];
            minIdx = i;
        }
    }
    return minIdx;
}

void Dijkstra(int start, int n) {
    distance[start] = 0; // 시작 정점의 거리 0으로 설정
	int curV;
    for (int i = 0; i < n; i++) {
        curV = extractMin(n); // 최소 거리 정점 추출 (현재 정점)
        if (curV == -1) { // 모든 정점을 방문했으면 종료
			return;
		}
        visited[curV] = 1;

        // 현재 정점의 모든 인접 정점 검사
        for (int j = 0; j < adjList[curV].edgeSize; j++) {
            int nextV = adjList[curV].edges[j].vertex; // 인접 정점
            int w = adjList[curV].edges[j].w; // 인접 정점으로의 가중치

            // 최단 거리 갱신 조건 확인
            if (!visited[nextV] && distance[curV] + w < distance[nextV]) {
                distance[nextV] = distance[curV] + w; // 최단 거리 갱신
            }
        }
    }
}

/*
5 7 1
1 2 1
1 4 5
5 1 10
3 5 3
4 3 1
3 1 2
2 3 2

8 12 7
1 2 1
2 4 2
4 7 7
3 6 1
6 1 4
7 6 9
7 8 1
1 3 2
2 7 5
1 4 1
2 5 2
7 5 2

5 3 2
1 2 1
1 3 1
1 4 1
*/

 

 

 

 

 

 

(전체코드) - 우선순위 큐 사용 - O(m log n)

// 무방향 양의 가중그래프
// 다익스트라 알고리즘 
// 우선순위 큐 사용 - O(m log n)
#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 100

typedef struct EDGE {
    int v;
    int w;
} EDGE;

// 인접 리스트를 나타내는 구조체
typedef struct EDGELIST {
    EDGE edge[MAX_NODES];
    int edgeSize;
} EDGELIST;

typedef struct MINHEAP {
    EDGE heap[MAX_NODES];
    int heapSize;
} MINHEAP;

EDGELIST adjList[MAX_NODES]; // 인접리스트 배열
int distance[MAX_NODES]; // 최단 거리 배열
int visited[MAX_NODES]; // 방문한 노드 배열

void initGraph(int n);
void addEdge(int u, int v, int w);
void initMinHeap(MINHEAP* h);
void push(MINHEAP* h, EDGE edge); // 최소 힙에 요소 추가 함수
EDGE pop(MINHEAP* h); // 최소 힙에서 최소 요소 제거 및 반환 함수
void Dijkstra(int start, int n);

int main() {
    int n, m, s;
    int u, v, w;

    scanf("%d %d %d", &n, &m, &s);
    initGraph(n);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &u, &v, &w);
        addEdge(u - 1, v - 1, w);
    }

    Dijkstra(s - 1, n);
    for (int i = 0; i < n; i++) {
        if (i != s - 1 && distance[i] != 2147483647) {
            // 시작 정점이 아니고 도달 가능한 정점인 경우 출력
            printf("%d %d\n", i + 1, distance[i]);
        }
    }
    return 0;
}

void initGraph(int n) {
    for (int i = 0; i < n; i++) {
        adjList[i].edgeSize = 0;
        distance[i] = 2147483647;
        visited[i] = 0;
    }
}

void addEdge(int u, int v, int w) {
    // 정점 u에 간선 추가
    adjList[u].edge[adjList[u].edgeSize].v = v;
    adjList[u].edge[adjList[u].edgeSize].w = w;
    adjList[u].edgeSize++;
    // 정점 v에 간선 추가 (무방향 그래프이므로 양쪽에 추가)
    adjList[v].edge[adjList[v].edgeSize].v = u;
    adjList[v].edge[adjList[v].edgeSize].w = w;
    adjList[v].edgeSize++;
}

void initMinHeap(MINHEAP *h) {
    h->heapSize = 0;
}

// 최소 힙에 요소 추가 함수
void push(MINHEAP* h, EDGE edge) {
    int i = (h->heapSize)++;

    // 힙 위로 올라가면서 적절한 위치를 찾음
    while (i > 0 && edge.w < h->heap[(i - 1) / 2].w) {
        h->heap[i] = h->heap[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    h->heap[i] = edge; // 적절한 위치에 요소 추가
}

// 최소 힙에서 최소 요소 제거 및 반환 함수
EDGE pop(MINHEAP* h) {
    EDGE min = h->heap[0]; // 최솟값 (루트)
    EDGE last = h->heap[--(h->heapSize)]; // 마지막 요소
    int i = 0, leftChildIdx;

    // 힙 아래로 내려가면서 적절한 위치를 찾음
    while (i * 2 + 1 < h->heapSize) {
        leftChildIdx = i * 2 + 1;
        if (leftChildIdx + 1 < h->heapSize && h->heap[leftChildIdx + 1].w < h->heap[leftChildIdx].w) {
            leftChildIdx++; // 오른쪽 자식이 더 작으면 오른쪽 자식 선택
        }
        if (last.w <= h->heap[leftChildIdx].w) {
            break; // 적절한 위치를 찾으면 중단
        }

        h->heap[i] = h->heap[leftChildIdx];
        i = leftChildIdx;
    }
    h->heap[i] = last; // 적절한 위치에 마지막 요소 배치
    return min; // 최솟값 반환
}

void Dijkstra(int start, int n) {
    MINHEAP* heap = (MINHEAP*)malloc(1 * sizeof(MINHEAP));
    initMinHeap(heap);

    distance[start] = 0; // 시작 정점의 거리 0으로 설정
    push(heap, (EDGE){start, 0}); // 힙에 시작 정점 추가
    while (heap->heapSize > 0) {
        EDGE minEdge = pop(heap); // 힙에서 최소 간선 추출
        int curV = minEdge.v; // 현재 정점
        if (visited[curV]) { // 정점을 이미 방문했다면 skip
            continue;
        }
        visited[curV] = 1;

        // 현재 정점의 모든 인접 정점 검사
        for (int i = 0; i < adjList[curV].edgeSize; i++) {
            int nextV = adjList[curV].edge[i].v; // 인접 정점
            int w = adjList[curV].edge[i].w; // 인접 정점으로의 가중치

            // 최단 거리 갱신 조건 확인
            if (!visited[nextV] && distance[curV] + w < distance[nextV]) {
                distance[nextV] = distance[curV] + w; // 최단 거리 갱신
                push(heap, (EDGE){nextV, distance[nextV]}); // 힙에 갱신된 정점 추가
            }
        }
    }

    free(heap);
}

/*
5 7 1
1 2 1
1 4 5
5 1 10
3 5 3
4 3 1
3 1 2
2 3 2

8 12 7
1 2 1
2 4 2
4 7 7
3 6 1
6 1 4
7 6 9
7 8 1
1 3 2
2 7 5
1 4 1
2 5 2
7 5 2

5 3 2
1 2 1
1 3 1
1 4 1
*/

 

 

 

 

 

 

 

문제2) 방향 가중그래프 -> 벨만-포드 알고리즘

방향 가중그래프(directed weighted graph) G와 출발정점이 주어지면, 출발정점에서 다른 모든 정점으로 가는 최단거리를 구하는 프로그램을 작성하라.

 

 

입력 그래프의 성질:
◦ n(1 ≤ n ≤ 100)개의 정점과 m(1 ≤ m ≤ 1,000)개의 간선으로 구성.
◦ 정점은 1 ~ n 사이의 정수로 번호가 매겨져 있고, 정점의 번호는 모두 다름.

◦ 모든 간선은 방향간선이고, 무게를 가진다(음의 가중치도 허용).
◦ 음의 사이클을 가지는 그래프는 입력되지 않는다고 가정.

 

◦ 입력

- 첫 줄에 정점의 개수 n, 간선의 개수 m, 출발정점 번호 s가 주어진다.

- 이후 m개의 줄에 한 줄에 하나씩 간선의 정보(간선의 양끝 정점 번호, 무게)가 주어진다. 가중치의 양의 최댓값은20을 넘지 않는다고 가정한다.

- 간선은 임의의 순서로 입력되고, 중복 입력되는 간선은 없다(방향간선이므로 간선 (u, v)와 (v, u)는 다른 간선으로 취급)

 

◦ 출력

- 출발정점 s에서 다른 모든 정점으로의 최단거리를 출력한다. 한 줄에 한 정점과 그

정점까지의 거리를 출력하되, 출력하는 순서는 정점의 번호의 오름차순으로 출력한다. 도달할 수 없는 정점은 출력하지 않는다.

 

 

 

 

 

 

 

(전체코드)

// 방향 가중그래프
// 벨만-포드 알고리즘
// O(nm)
#include <stdio.h>
#include <stdlib.h>

#define MAX_NODES 100

typedef struct EDGE {
    int u, v;
    int w;
} EDGE;

EDGE edge[MAX_NODES * MAX_NODES]; // 간선 배열
int distance[MAX_NODES]; // 최단 거리 배열

void initGraph(int n);
void BellmanFord(int start, int n, int m);

int main() {
    int n, m, s;

    scanf("%d %d %d", &n, &m, &s);
    initGraph(n);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].w);
        edge[i].u--; // 0 기반 인덱스로 변경
        edge[i].v--; // 0 기반 인덱스로 변경
    }

    BellmanFord(s - 1, n, m);
    for (int i = 0; i < n; i++) {
        // 시작 정점이 아니고 도달 가능한 정점인 경우 출력
        if (i != s - 1 && distance[i] != 2147483647) {
            printf("%d %d\n", i + 1, distance[i]);
        }
    }

    return 0;
}

void initGraph(int n) {
    for (int i = 0; i < n; i++) {
        distance[i] = 2147483647;
    }
}

void BellmanFord(int start, int n, int m) {
    distance[start] = 0; // 시작 정점의 거리 0으로 설정
    for (int i = 0; i < n - 1; i++) { // 총 n - 1번 반복
        for (int j = 0; j < m; j++) { // 모든 간선에 대해 반복
            int u = edge[j].u; // 간선의 시작 정점
            int v = edge[j].v; // 간선의 끝 정점
            int w = edge[j].w; // 간선의 가중치

            // 최단 거리 갱신 조건 확인
            if (distance[u] != 2147483647 && distance[u] + w < distance[v]) {
                distance[v] = distance[u] + w; // 최단 거리 갱신
            }
        }
    }
}

/*
5 7 1
1 2 1
1 4 5
5 1 -2
3 5 3
3 4 1
1 3 2
3 2 -3

4 5 1
1 2 1
2 3 -2
3 1 2
3 4 1
1 4 5
*/

 

 

 

 

 

 

https://www.youtube.com/watch?v=XIwiZZr2l5I&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=31

 

다익스트라 알고리즘에 대해 이 영상을 참고하자

 

 

 

https://www.youtube.com/watch?v=061eXyAFRuI&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=32

 

벨만-포드 알고리즘에 대해 이 영상을 참고하자

 

 

 

 

 

 

 

 

출처 및 참고: 알고리즘-원리와 응용(국형준교수님)