'다익스트라' 태그의 글 목록

(뭐 대충 중요하다는 내용ㅎ) 최단 경로 문제를 풀 때 가장 많이 언급되고 활용되는 삼대장이 있죠? 다익스트라 벨만포드 플로이드 상황에 맞게 위 알고리즘을 적용해서 문제를 해결하면 될텐데 언제, 무엇을 선택할 지 모르겠다면 3가지를 떠올려봅시다. 문제를 그래프화 하는 것에 성공하셨다면 이제 이 3가지 흐름을 생각해 봅시다. 가중치가 있는가? : 가중치가 없다면 BFS로 해결 가능 음수간선이 있는가? : weight에 음수 값이 있다면 벨만포드 단일 시작점을 갖는가? : 단일 시작점이 주어진다면 다익스트라, 모든 정점들의 쌍에 대한 경로 값을 알고 싶다면 플로이드 어떤 알고리즘을 쓰면 되는지 선택하셨다면 각 알고리즘들의 개념을 짚어보도록 하겠습니다. 오늘은 Dijkstra Algorithm에 대해 먼저 살..