그래프에서 가장 짧은 순환 경로를 얻는 방법은 무엇입니까?

Question

나는 하나의 도시에서 다른 도시로가는 최단 경로를 계산하기위한 간단한 프로그램을 개발 중이다. 그래프의 지시 가중치 노드를 사용하여 기차 트레일 맵을 나타낸다.

은 지금까지 나는 Bellman-Ford, Dijkstra, Floyd-Warshall 및 Johnson 알고리즘을 시도하고 그들 모두는 시작과 동일하지 않습니다 다른 목적지까지의 최단 경로를 찾을 좋다.

다른 도시를 통해 도시 A와 도시 A 사이의 경로를 계산해야 할 때, 도시에서 자체 경로를 무시하기 때문에 항상 0 값을 얻습니다. 무한 루프.

는 나는이 대상 노드를 잡는다 때 중지 알고리즘을 목표로 target을 또 다른 매개 변수를 작성하여 그 루프 문제를 해결하는 것이 간단 할 수 있음을 알고,하지만 난 중 하나를 수정할 수있는 능력이없는 그 도서관들.

누구나 나를 보여줄 수 있습니까?

내 그래프 AB5 - BC4 - CD8 - DC8 - DE6 - AD5 - CE2 - EB3 - AE7하고 BB까지의 거리가 9을해야하지만, 모든 알고리즘에이 0를 반환합니다.

참고 : StackOverflow 및 Google에서 적어도 Java에서는 검색 할 때 처음부터 끝까지 경로를 찾는 데 아무도 귀찮게하지 않으므로 중복되지 않습니다.

Answer 1

간단한 접근법은 수정 된 그래프로 이미 가지고있는 최단 경로 알고리즘/라이브러리를 사용하는 것입니다. 각 노드와 해당 인접한 나가는 모서리를 복제 한 다음 복제 된 노드에서 원래 노드로 최단 경로를 찾을 수 있습니다. 여기

는 변환 (편의상 무게없이) AA 경로 같을 것이다 방법입니다

아마