0
지하철 네트워크에서 작업하고 있습니다. A와 B 사이의 몇 가지 경로, 예를 들어, 가장 빠른, 가장 짧은 등을 존중하는 경로를 찾아야합니다 ... 나는 그것들을 해결하는 방법을 알고 있습니다. 그러나 규칙들 중 하나는 줄 사이의 변화가 적은 경로를 찾는 것입니다. 그것에 사용 된 알고리즘이 있습니까?변경 사항이 적은 경로를 얻는 데 가장 좋은 알고리즘
A
답변
3
그래프에서 노드로 지하철 선을 처리하고 두 개의 지하철 선이 교차하는 경우 가장자리로 두 노드를 연결합니다. 이제 Dijkstra's algorithm을 사용하여 최단 경로를 찾을 수 있습니다.
+0
감사합니다. 나는 그 접근법을 사용하여 그것을 할 수있었습니다! – lulas
다른 사람들과 어떻게 다른지 알지 못합니다. 기차를 갈아 타기 위해 여행 시간에 임의의 지연을 추가 한 다음, '가장 빠른'알고리즘을 사용하여 변경이 적은 경로를 찾으십니까? –