안녕하세요. 이번 시간에는 단일 출발지에서 최단 경로를 찾는 다익스트라 알고리즘에 대해 알아보겠습니다.

단일 출발지에서 최단 경로가 무슨 소리냐면, 한 버텍스에서 다른 모든 버텍스까지의 최단 경로를 찾는다는 소리입니다.

즉 다익스트라 알고리즘을 사용하여 A로부터 시작하면, B, C, D, E, F 모든 버텍스에 대한 최단 경로를 구할 수 있습니다.

일단 모든 버텍스의 최단 거리값을 Infinity(무한)으로 설정합니다. 

그리고 시작점(A) 최단 거리값을 0으로 설정합니다. 이제 A와 연결된 B, C의 거리값을 조정하는데, 시작점 거리값에 아크 값을 더한 것보다 도착점 거리값이 크면 도착점 거리값을 더한 값으로 낮춥니다.

무슨 말인지 글로 보면 헷갈리죠? 

시작점 거리값(A, 0)에 아크 값(6)을 더한 것(0+6 = 6)보다 도착점 거리값(B, 무한)이 크면 도착점 거리값을 더한 값(6)으로 바꿉니다. 

이제 B는 6이 되는 거죠. C도 0 + 3보다 무한(C값)이 더 크기 때문에 C는 3이 됩니다.

이제 A(0), B(6), C(3), 나머지는 무한인 상황에서 B를 기준으로 반복합니다. A, C, D가 연결되어 있습니다.

A에서는 B + 아크(6 + 6)보다 A(0)가 작기 때문에 넘어갑니다. 

C에서는 B + 아크(6 + 2)보다 C(3)가 작기 때문에 역시 넘어갑니다. 

D에서는 B + 아크(6 + 5)보다 D(무한)이 크기 때문에 D값을 11로 낮춥니다.

A(0), B(6), C(3), D(11), 나머지는 무한인 상황에서 C를 기준으로 반복합니다.

 A, B, D, E가 연결되어 있습니다. A에서는 C + 아크(3 + 3)보다 A(0)이 작기 때문에 넘어갑니다.

 B에서는 C + 아크(3 + 2)보다 B(6)가 크기 때문에 B값을 5로 낮춥니다. 

D에서는 C + 아크(3 + 3)보다 D(11)이 크기 때문에 D값을 6으로 낮춥니다. 

E에서는 C + 아크(3 + 4)보다 E(무한)값이 크기 때문에 E의 값을 7로 낮춥니다.

이제 A(0), B(5), C(3), D(6), E(7), F(무한)입니다. 

이렇게 남은 D, E, F에서도 반복하면 모든 버텍스의 최단 거리가 나옵니다. 

거리가 짧을 때만 값을 낮추고, 크면 넘어가기 때문에 최단 거리를 찾을 수 있는 겁니다.

다익스트라 알고리즘은 기본적으로 동적 프로그래밍도 가능하지만 그리디 알고리즘으로 최적화할 수 있다는 점에서 프림 알고리즘과 상당히 비슷합니다. 

사실상 프림 알고리즘을 살짝 변형한 것과 다름없습니다.

    this.data = data; // weight of the edge

Graph.prototype.insertVertex = function(key) {

Graph.prototype.insertArc = function(data, fromKey, toKey) {

    const fromVertex = this.findVertex(fromKey);

    const toVertex = this.findVertex(toKey);

Graph.prototype.findVertex = function(key) {

다익스트라 알고리즘

Body Parser란?