다익스트라 알고리즘

 

 

기존의 DFS는 가까운 노드를 방문한 후 무작위 노드를 방문하여 탐색하는 방식이었다.

하지만 이 알고리즘은 간선간의 비용을 고려하지 않는 알고리즘이다.

만약 간선간의 비용이 존재한다면, DFS 알고리즘의 최적의 길은 효율적인 길인지는 의문을 품어야한다.

 

그에 필요성에 나온 알고리즘이 다익스트라 알고리즘이다.

 

 

위의 그림을 보자.

만약 DFS라면 출발점이 0 이고, 도착점이 5라면,

0->3->4->5 순이 최적의 길이라고 말할 수 있다.

하지만 비용적 측면에서 봤을때, 가장 효율적인 길은 0->1->3->4->5 이다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
using namespace std;

// 비용적인 경로를 생각하여 경로를 탐색한다.


struct Vertex
{
	// data
};

vector<Vertex> vertices; // 데이터 동적배열 노드을 만든다.
vector<vector<int>> adjacent; // 간선을 만든다.

void CreateGraph()
{
	vertices.reserve(6);
	adjacent = vector<vector<int>>(6, vector<int>(6, -1));

	adjacent[0][1] = 15;
	adjacent[0][3] = 35;

	adjacent[1][0] = 15;
	adjacent[1][2] = 5;
	adjacent[1][3] = 10;

	adjacent[3][4] = 5;
	adjacent[5][4] = 5;
}


void Dijikstra(int here)
{
	struct VertextCost
	{
		int vertex;
		int cost;
	};

	list<VertextCost> discovered; // 발견 목록
	vector<int> best(6, INT32_MAX); // 각 정점별로 지금까지 발견한 최소 거리
	vector<int> parent(6, -1);

	// 시작점을 방문한다. 
	discovered.push_back(VertextCost{ here , 0 });
	best[here] = 0;
	parent[here] = 0;

	while (discovered.empty() ==false)
	{
		//제일 좋은 후보를 찾는다.
		list<VertextCost>::iterator bestlt;
		int bestCost = INT32_MAX; // 임의의 값을 넣는다.

		for (auto it = discovered.begin(); it != discovered.end(); it++)
		{
			const int vertex = it->vertex;	// 0	
			const int cost = it->cost;		// 0

			if (cost < bestCost)	// 0 < 2147483647
			{
				bestCost = cost; // bestCost = 0
				bestlt = it;		// bestlt = 0
			}
		}

		int cost = bestlt->cost; //cost = 0
		here = bestlt->vertex;
		discovered.erase(bestlt); // 방문 리스트에서 삭제

		// 방문? 더 짧은 경로를 뒤늦게 찾았다면 스킵.
		if (best[here] < cost)
			continue;

		//방문
		for (int i = 0; i < 6; i++)
		{
			// 연결되지 않았으면 스킵.
			if (adjacent[here][i] == -1)
				continue;

			//더 좋은 경로를 과거에 찾았으면 스킵.
			int nextCost = best[here] + adjacent[here][i]; // 0의 경우 15 / 35
			if (nextCost >= best[i]) // 35 탈락
				continue;

			best[i] = nextCost;		// best[1] = 15; //best[3] = 35 
			parent[i] = here;		//parent[1] = 0; // parent[3] = 0;
			discovered.push_back(VertextCost{i, nextCost});

			//discoverd => 2 {1, 15} {3, 35};
		}

	}
	int a = 3;
}
int main()
{
	CreateGraph();


	Dijikstra(0);
}

첫번째 0일때, while 문을 적어놓았다.  이러한 과정이 반복되서 최종 비용이 적은 노드를 찾게 된다. 하지만 for문에서 계속 방문하여 최적의 노드를 찾아야 된다는 점에서 코드 효율적인 면에서 시간소요가 오래걸리게 된다. 그러므로 후에 배울 우선순위 큐를 구현하여 연습하여야 한다.

 

▶ auto 키워드란?

auto는 부르는 사람에 따라서 조금씩 다르게 불리는데요.

이런식으로 불리곤 합니다.  "타입 추론", "데이터 타입 추론", "자동 데이터 추론", "초기화 값에 따라 알아서 데이터 타입을 정해주는 키워드"

auto 키워드는 선언한 변수나 람다식의 타입을 컴파일러에게 추론하도록 맡깁니다.

 

정리를 하자면 "auto는 초기화 값에 따라 알아서 데이터 타입을 정해주는 키워드" 입니다.