[Greedy] Dijkstra Algorithm

다익스트라 알고리즘

 

최단거리를 찾는 알고리즘입니다.

{ 최소거리 노드 고정, 고정되지 않은 노드들의 거리를 수정 } 을 반복합니다.

 

ex)

start A

-> A 0 고정

 

    A B C D E F

    0 4 2 ∞ ∞ ∞

-> C 2 고정, 나머지 수정

 

    A B C D E F

    0 3 2 9 ∞ ∞

-> B 3 고정, 나머지 수정

 

    A B C D E F

    0 3 2 9 6 ∞

-> E 6 고정, 나머지 수정

 

    A B C D E F

    0 3 2 8 6 11

-> D 8 고정, 나머지 수정

 

    A B C D E F

    0 3 2 8 6 9

-> F 9 고정

 

    A B C D E F

    0 3 2 8 6 9