다익스트라 알고리즘 편집하기 (부분)

==예시==

=== 기본 예시 ===
다음은 가중치가 있는 그래프에서 시작 정점 A에서 다른 모든 정점까지의 최단 경로를 구하는 예이다.

그래프:
 A --(4)--> B --(1)--> C
  \         |
   \       (2)
    \       v
     (2)--> D
'''단계별 계산'''

다익스트라 알고리즘을 통해 A에서 시작해 모든 정점까지의 최단 경로를 구하는 과정을 표로 나타내면 다음과 같다.
{| class="wikitable"
!단계!!기준점!!B까지 거리!!C까지 거리!!D까지 거리!!비고
|-
|0||A||∞||∞||∞||초기화
|-
|1||A||4||∞||2||A → B(4), A → D(2) 직접 연결됨
|-
|2||D||4||∞||2||
* A와 거리가 가장 가까웠던 D 선택
* D를 거쳐서 더 짧아지는 경로 없음
|-
|3||B||4||5||2||
* 그 다음 A와 거리가 가장 가까웠던 B 선택
* C로 갈 수 있게 됨
|-
|4||C||4||5||2||
* 마지막으로 방문하지 않은 C 선택
* 변동 없음
|}최종적으로 각 정점까지의 최단 거리는 다음과 같다:
*A: 0
*B: 4
*C: 5
*D: 2

=== 좀 더 어려운 예시 ===
[[파일:방향 그래프.png|400x400픽셀]]
{| class="wikitable"
!단계!!기준점
!A!!B!!C!!D
!E
!F
!G
!H!![[우선순위 큐]]
|-
|0||A
|0||∞||∞||∞
|∞
|∞
|∞
|∞||B(∞), C(∞), D(∞), E(∞), F(∞), G(∞), H(∞)


|-
|1||A
|'''(0)'''||1||5||11
|
|
| ||

|B(1), C(5), D(11)


|-
|2||B
| ||'''(1)'''||3||
|11
|
|
| ||C(3), D(11), E(11)


|-
|3||C
| || ||'''(3)'''||
|9
|4
|
| ||F(4), E(9), D(11)




|-
|4||F
| || || ||
|8
|'''(4)'''
|7
|5||H(5), G(7), E(8), D(11)
|-
|5
|H
|
|
|
|
|7
|
|6
|'''(5)'''
|G(6), E(7), D(11)
|-
|6
|G
|
|
|
|7
|
|
|'''(6)'''
|
|E(7), D(7)
|-
|7
|E
|
|
|
|
|'''(7)'''
|
|
|
|D(7)
|-
|8
|D
|
|
|
|'''(7)'''
|
|
|
|
|
|}

=== 음의 값을 넣을 수 없는 예시 ===