Dijkstra1 [개념] Dijkstra(다익스트라) - python 다익스트라 알고리즘 - 유향 그래프에서 간선들의 가중치가 모두 0 이상인 경우의 최단 경로 알고리즘 왜 가중치가 0 이상이어야 할까? - 다익스트라 알고리즘에서 최단 거리를 저장한 노드는 집합에 포함시켜 놓는데, 집합에 포함된 노드의 최단 거리 값은 다시 계산하지 않는다. 그러나 가중치가 음수일 경우, 최단 거리 값이 바뀌어 노드에 저장해 놓은 최단 거리 값을 바꿔야하는 경우가 발생할 수도 있다. 하지만 집합에 포함된 노드는 값을 수정할 수 없기 때문에 다익스트라 알고리즘은 간선의 모든 가중치가 0 이상일 때 성립한다. 다익스트라 알고리즘에서의 가정 두 정점 간 경로가 존재하지 않으면 경로의 가중치는 무한대로 정의한다. 두 정점 간 간선이 존재하지 않으면 가중치가 무한대인 간선이 존재한다고 간주한다. 다.. 2022. 3. 24. 이전 1 다음
