shortest path (1) 썸네일형 리스트형 114. Shortest Path 최단 경로(Shortest Path)는 그래프에서 정점과 정점 사이의 경로 중 길이가 가장 짧은 것을 의미하며 그래프 이론에서 기본적인 내용으로 많이 다루어지는 주제이다. 일반적으로 최단 경로를 찾는 대상은 그래프의 정점으로, 트리에서의 최단 경로는 복잡한 요소가 없기 때문에 최단 경로라는 주제로 따로 분리하지 않는다. 아래의 내용이 끝이다. 가중치가 음수인 간선이 하나라도 있다면 그 간선을 무한히 왕복하는 것이 가능하므로 모든 최단 경로의 길이가 $-\infty$가 되며, 가중치가 음수인 간선이 없다면 두 정점 사이의 단순 경로가 두 정점 사이의 최단 경로와 같다. 그래프는 두 정점 사이에 여러 경로가 존재할 수 있으므로 최단 경로를 구하는 것이 더 흥미로운 주제가 된다. 그래프에서 최단 경로를 구하는.. 이전 1 다음
