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

내용 삭제됨 내용 추가됨
편집 요약 없음
TedBot (토론 | 기여)
잔글 봇: 빈 문단 정리
19번째 줄:
2 '''for each''' vertex v in V[G] ''// 초기화''
3 d[v] := infinity
4 previous[v] := undefined
5 d[s] := 0 ''//덮어쓰기''
6 S := empty set
26번째 줄:
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 ''//경로 추적할 때 쓰임//''
34번째 줄:
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]
66번째 줄:
* [http://students.ceid.upatras.gr/~papagel/english/java_docs/minDijk.htm 대화형 구현]
 
== 각주 ==
{{각주}}
 
[[분류:그래프 알고리즘]]