편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
246번째 줄: | 246번째 줄: | ||
==== 데이크스트라(Dijkstra) 알고리즘 ==== | ==== 데이크스트라(Dijkstra) 알고리즘 ==== | ||
{{--|이거 왜 그리디에 없고 여기 있냐}} 유향 그래프에서 간선의 가중치가 모두 음이 아닌 정수일 때, 출발지에서 목적지까지의 최단거리를 찾는 알고리즘이다. 움짤이 여럿 돌아다니니 한 번 보자. | {{--|이거 왜 그리디에 없고 여기 있냐}} 유향 그래프에서 간선의 가중치가 모두 음이 아닌 정수일 때, 출발지에서 목적지까지의 최단거리를 찾는 알고리즘이다. 움짤이 여럿 돌아다니니 한 번 보자. | ||
[[ | [[File:Shortest path Dijkstra vs BellmanFord.gif|thumb|Shortest path Dijkstra vs BellmanFord]] | ||
{{--|c부터 조사하지 않는 게 수상하긴 하지만 }}윗 것은 데이크스트라, 아랫 것은 벨먼 포드 알고리즘이다. 이것만 보고도 이해할 수 있다면 참 좋겠다. <!-- 다음은 그 소스이다. c로 구현하기 힘든데...--> | {{--|c부터 조사하지 않는 게 수상하긴 하지만 }}윗 것은 데이크스트라, 아랫 것은 벨먼 포드 알고리즘이다. 이것만 보고도 이해할 수 있다면 참 좋겠다. <!-- 다음은 그 소스이다. c로 구현하기 힘든데...--> | ||