다익스트라 알고리즘 규칙

핵심.

P[A][B] 2차 배열로 Size만큼 간선의 길이를 만든다.


vertices.resize(6);
	adjacent = vector<vector<int>>(6, vector<int>(6, -1));
	// -1 - 1 - 1 - 1 - 1  
	// -1 - 1 - 1 - 1 - 1  
	// -1 - 1 - 1 - 1 - 1  
	// -1 - 1 - 1 - 1 - 1  
	// -1 - 1 - 1 - 1 - 1  
	// -1 - 1 - 1 - 1 - 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;

출발점으로부터 최단거리를 저장할 배열 d[v]를 만들자.

출발 노드에는 0을 출발점을 제외한 다른 노드들에게는 매운 큰 값 INF를 채워 넣는다. (정말 무한으로 간주될 수 있는 값을 의미)


vector<int> best(_size, INT32_MAX);
	best[here] = 0;

1.현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장한다.


int A = here;

1.도착 노드가 "방문 완료" 상태가 되거나, 혹은 더 이상

미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.

→ 3,7의 과정은?

3. A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B]와 d[B]의 값을 비교한다. INF와 비교할 경우 무조건 전자가 작다.

4. 만약 d[A] + P[A][B]의 값이 더 작다면, 즉 더 짧은 경로라면, d[B]의 값을 이 값으로 갱신시킨다.

5. A의 모든 이웃 노드 B에 대해 이 작업을 수행한다.

A의 상태를 "방문 완료"로 바꾼다. 그러면 이제 더 이상 A는 사용하지 않는다.

미방문" 상태인 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드 하나를 골라서 그 노드를 A에 저장한다.

그럼 우선, 3 ~ 7 을 반복할 수 있도록 while문을 만들고, 방문완료를 알 수 있는 변수를 하나 더 선언해주어야 할 것 같다.


struct VertexCost {
		int vertex;
		int cost;
	};

discovered.push_back(VertexCost{ here,0 });
	while (discovered.empty() == false)
	{
		
	}