다익스트라 알고리즘1 [Java] 다익스트라 (Dijkstra) 최단 경로 알고리즘 다익스트라 (Dijkstra) 알고리즘 하나의 시작 정점으로부터 모든 다른 정점까지의 음의 가중치가 없을 때 최단 경로를 찾는 알고리즘 다익스트라 알고리즘에서 음수 간선이 존재하면 안 되는 이유 다익스트라 알고리즘의 각 단계 먼저 집합 S를 시작 정점 v로부터의 최단경로가 이미 발견된 정점들의 집합이라고 하자. 다익스트라 알고리즘에서는 시작 정점에서 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단거리를 기록하는 배열이 반드시 있어야 한다. 이 1차원 배열을 distance라고 한다. 시작 정점을 v라 한다면 distance[v] = 0이고, 다른 정점에 대한 distance값은 시작 정점과 해당 정점 간의 가중치 값이 된다. 가중치 인접 행렬을 weight라 하면 distance[w] = wei.. 2021. 3. 12. 이전 1 다음 728x90 반응형
