mondegreen

최단 경로의 개념 간선의 가중치가 있는 그래프에서 "두 정점 사이의 경로들 중"에 간선의 가중치의 합이 최소인 경로 1) 다익스트라(음의 가중치 허용하지 않음) 2) 벨만-포드(음의 가중치 허용함) 다익스트라의 개념 시작 정점에서 끝 정점까지 거리가 최소인 정점을 선택해가며 최단 경로를 구하는 방식 프림과 유사하나 당장의 가중치 한 개의 값이 아닌 "가중치의 합"을 고려해야 하는 알고리즘이다. 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 다익스트라 동작 과정 1) 시작 정점 선택 2)..