#7 다익스트라의 최단 경로

다익스트라의 최단 경로

1.각 간선에 대한 정보를 우선순위 큐에 담아 처리하는 방식으로 동작 원리가 프림 알고리즘과 흡사하다.

2.다익스트라의 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다.

3.현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에 적합한 알고리즘이다.

 

 

 

동작방식

 

1.그래프의 시작점을 선택해 트리T에 포함시킨다.

2.T에 포함된 노드와 T에 포함되지 않은 노드 사이의 간선 중에서 '이동거리'가 가장 작은 간선을 찾는다.

3.해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함시킨다.

4.  모든 노드가 포함될 때까지 2와 3과정을 반복한다.

 

다익스트라의 최단경로 (위키백과)

코드예시

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define NODE_MAX 20001
#define EDGE_MAX 600001  //양 방향 간선이므로 30만개


typedef struct {
	int cost;
	int node;
} Edge;


void swap(Edge* a, Edge* b) {
	Edge temp;
	temp.cost = a->cost;
	temp.node = a->node;
	a->cost = b->cost;
	a->node = b->node;
	b->cost = temp.cost;
	b->node = temp.node;
}


typedef struct {
	Edge* heap[EDGE_MAX];
	int count;
}priorityQueue;

void push(priorityQueue* pq, Edge* edge) {
	if (pq->count >= EDGE_MAX)return;
	pq->heap[pq->count] = edge;
	int now = pq->count;
	int parent = (pq->count - 1) / 2;
	//새 원소를 삽입한 이후에 상향식으로 힙 구성
	while (now > 0 && pq->heap[now]->cost < pq->heap[parent]->cost) {
		swap(pq->heap[now], pq->heap[parent]);
		now = parent;
		parent = (parent - 1) / 2;
	}
	pq->count++;
}

Edge* pop(priorityQueue* pq) {
	if (pq->count <= 0) return NULL;
	Edge* res = pq->heap[0];
	pq->count--;
	pq->heap[0] = pq->heap[pq->count];
	int now = 0, leftChild = 1, rightChild = 2;
	int target = now;
	//새 원소를 추출한 이후에 하향식으로 힙을 구성
	while (leftChild < pq->count) {
		if (pq->heap[target]->cost > pq->heap[leftChild]->cost) target = leftChild;
		if (pq->heap[target]->cost > pq->heap[rightChild]->cost && rightChild < pq->count) target = rightChild;
		if (target == now) break;
		//더 이상 내려가지 않아도  될 때 종료
		else {
			swap(pq->heap[now], pq->heap[target]);
			now = target;
			leftChild = now * 2 + 1;
			rightChild = now * 2 + 2;
		}
	}
	return res;
}

//다익스트라 알고리즘 간선연결리스트구현(프림과 같음)
typedef struct Node {
	Edge* data;
	struct Node* next;

}Node;

Node** adj;
int ans[NODE_MAX];


void addNode(Node** target, int index, Edge* edge) {
	if (target[index] == NULL) {
		target[index] = (Node*)malloc(sizeof(Node));
		target[index]->data = edge;
		target[index]->next = NULL;
	}
	else {
		Node* node = (Node*)malloc(sizeof(Node));
		node->data = edge;
		node->next = target[index];
		target[index] = node;
	}
}

//다익스트라 알고리즘 사용

int main(void) {
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	adj = (Node**)malloc(sizeof(Node*)*(n+1));  //노드의 갯수만큼 연결리스트 구현
	for (int i = 1; i <= n; i++) { 
		adj[i] = NULL;
		ans[i] = INT_MAX;  //모든 노드로 갈수있는 비용을 무한으로 설정
   }
	priorityQueue* pq;
	pq = (priorityQueue*)malloc(sizeof(priorityQueue));
	pq->count = 0;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c); 
		//a->b로 가는 거리가 C이다.
		Edge* edge = (Edge*)malloc(sizeof(Edge));
		edge->node = b;
		edge->cost = c;
		addNode(adj, a, edge);
	}
  //다익스트라 알고리즘 시작
	ans[k] = 0;   
	//출발하고자 하는 노드를 K라 설정 (비용을0으로 설정)
	Edge* start = (Edge*)malloc(sizeof(Edge));
	start->cost = 0; start->node = k; push(pq, start);
	//출발 노드에 대한 간선 정보를 큐에다 넣는다.
	while (1) {
		Edge* now = pop(pq);
		if (now == NULL) break;
		int curNode = now->node;
		int curCost = now->cost;
		//하나를 꺼내서, 노드랑 비용정보를답는다. 
		if (ans[curNode] < curCost) continue;
		//현재 보고있는 비용이 테이블에 담은 비용보다 더 크다면, 그냥 무시한다.
		Node* cur = adj[curNode];  //노드의 집합 트리T adj
		//그렇지 않다면, 추가시킨다.
		while (cur != NULL) {
			Edge* temp = cur->data;
			temp->cost += curCost;
			//건너가는 비용을 코스트에 담는다.
			if (temp->cost < ans[temp->node]) { ans[temp->node] = temp->cost; push(pq, temp);}
			//현재 테이블에 담겨있던 해당 노드의 대한 최단거리 비용이 현재 보고있는 비용보다 크다면, 더 작은값으로 갱신시켜준다.
			//그 뒤에 간선에 다시 담는다.
			cur = cur->next;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (ans[i] == INT_MAX) printf("INF\n");
		else printf("%d\n", ans[i]);
	}
	system("pause");
}

 

 

 

결과값

3 3 1   정점의 개수3, 간선의 개수 3, 출발지점 1
1 2 10   1->2 비용 10
1 3 30   1->3 비용 30
2 3 5    2->3 비용 5
0    1까지 비용 0 (스타트지점)
10  1->2까지 비용 10
15  1->3까지 비용 15 ( 1->2 10소요, 2->3 5소요    10+5=15)

 

 

 

다익스트라의 최단 알고리즘은 프림 알고리즘처럼 O(ElogV)의 시간 복잡도를 가진다.