0
안녕하세요 저는이 질문에 어려움을 겪고 있습니다.Dijkstra 's를 사용하여 가중치가 적용된 그래프에서 최저 가중치 사이클을 찾습니다.
weighted, directed 그래프에서 가장 낮은 가중치 사이클 (즉, 그래프의 모든 사이클 중 에지 가중치가 가장 작은 사이클)을 찾는 알고리즘을 고안합니다. G = (V, E). 런타임 및 공간의 복잡성을 간단히 정당화하십시오. 모든 모서리가 음수가 아닌 것으로 가정합니다. 그것은 O (| V || E | log | V |) 시간에 실행되어야합니다. 힌트 : Dijkstra의 알고리즘을 여러 번 호출하십시오.
Floyd-Warshall을 사용하는 솔루션을 보았지만 Dijkstra를 사용하여 어떻게이를 수행 할 것이며 시간 제약 조건 내에서이를 수행하는 방법에 대해 궁금합니다.
첫째- , 우리가 어떻게도 그래프에 얼마나 많은 사이클을 알고 및 그 확인 방법 : 나는 혼란의 몇 가지 포인트가?
- 또한, 왜 | E || V | log | V | 내 이해에 따라 모든 꼭지점을 통해 을 통과해야하므로 | V | log | V |가됩니다.
내 개인 학습용이므로 누구나 사용할 수있는 예제가 있다면 큰 도움이 될 것입니다. 저는 의사 코드를 찾고 있지 않습니다. 한 노드에서 모든 노드로 최단 경로를 사용하는 것이이 문제를 해결하는 데 어떻게 도움이되는지를 이해하는 일반적인 알고리즘입니다. 감사합니다.