"데이크스트라 알고리즘"의 두 판 사이의 차이

잔글
봇: 빈 문단 정리
잔글 (봇: 빈 문단 정리)
2 '''for each''' vertex v in V[G] ''// 초기화''
3 d[v] := infinity
4 previous[v] := undefined
5 d[s] := 0 ''//덮어쓰기''
6 S := empty set
9 u := Extract_Min(Q) ''//집합 Q에서 d[u]가 최소인 u를 찾아 빼냄''
10 S := S union {u} ''//빼낸 u를 S에 삽입''
11 '''for''' each v with edge (u,v) defined
12 '''if''' d[v] > d[u] + w(u,v)
13 d[v] := d[u] + w(u,v) ''// 변(u,v)의 경감''
14 previous[v] := u ''//경로 추적할 때 쓰임//''
previous[]가 구해지면, 이를 이용해 다음과 같이 ''s''에서 ''t''까지의 최단 경로를 얻을 수 있다.
 
1 S := empty sequence
2 u := t
3 '''while''' defined u
4 insert u to the beginning of S
5 u := previous[u]
* [http://students.ceid.upatras.gr/~papagel/english/java_docs/minDijk.htm 대화형 구현]
 
== 각주 ==
{{각주}}
 
[[분류:그래프 알고리즘]]

편집

1,379,342