tonirr

최단경로 가중방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로 플로이드 알고리즘 모든 정점 간의 최단 경로 동적 프로그래밍 방법 적용 O(|V|^3) 가중치의 합이 음수인 사이클이 없다고 가정 플로이드 Floyd 알고리즘 다익스트라 Dijkstra 알고리즘 모든 정점 간의 최단 경로 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로 (단일 출발점 최단 경로) 동적 프로그래밍 방법 적용 그리디 방법 적용 O(|V|^3) O(|V|^2) 가중치의 합이 음수인 사이클이 없다고 가정 음의 가중치를 갖는 간선이 없다고 가정 다익스트라 알고리즘 거리 d[v] 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이 출발점에서 시작하여 거리 d[..