dijkstra를 사용하여 정확히 하나의 네거티브 에지가있을 때 모든 단일 소스 최단 경로를 찾는 문제를 해결할 수있었습니다.K 네거티브 에지 - 단일 소스 최단 경로
이제 dijkstra (bellman ford 제외)를 사용하여 K 개의 음수 에지가있는 경우 주어진 소스에서 모든 최단 경로를 찾는 방법에 대해 새로운 문제에 직면하고 있습니다. (k는 알려져 있음).
정말 좋은 방법이라고 생각하지 마십시오.
제안 사항?
무 지향성 그래프 인 경우 단 하나의 최단 경로가 있어도 그 네거티브 에지를 앞뒤로 건너 뛰고 무한 수의 경로가 음의 무한대가 될 수 있기 때문에 단 하나의 최단 경로는 없습니다.
그러나 부정적인 사이클이없는 방향성 그래프를 가정하면 처음 검색을 사용하고 이미 충돌 한 네거티브 에지와 지금까지 발견 한 각 노드의 최단 경로를 추적 할 수 있습니다. 이미 방문한 노드가 표시되면 이전에 얻은 경로보다 더 나은 경우에만 다시 노드로 이동하십시오.
부정적인주기가 없으므로 알고리즘을 종료해야합니다. 알고리즘이 종료 된 후 대상 노드는 거기에 도달하는 데 사용 된 최상의 경로를 가져야합니다.
부정적인주기가 있다면? 최단 경로는 없을 것입니다. 작업에 잘못된 도구를 사용하고 싶지 않을 때는 포크를 사용하여 나사를 조이는 것과 같습니다. –
음, Dijkstra 만 사용하여 해결할 수있는 방법이 있다는 것을 알고 있습니다. 음수 사이클이 없다고 가정 할 수도 있습니다. – Rouki
관련 항목? http://cs.stackexchange.com/questions/2482/using-dijkstras-algorithm-with-negative-edges – BlackBear