Algorithms, 4th edition, Robert Sedgewick and Kevin Wayne에서 아래의 문제가 발생했을 때 최단 경로 알고리즘을 가장 최근에 알고있었습니다.Bellman Ford 알고리즘이 방향성 가중 그래프의 최단 경로를 계산하지 못했습니다.
는 조각 내 code 구현 벨만 포드 알고리즘 (큐 기반) : 나는 종이에 많은 예를하려고했으나 방향 그래프가 생성 시나리오를 찾을 수없는 생각했습니다는 EdgeWeightedGraph의 각 에지에 대해 EdgeWeightedDigraph (각 방향으로 하나)의 두 DirectedEdge 객체를 생성하여 우리가 방향성 EdgeWeightedGraph 내로 EdgeWeightedGraph 변환한다고 가정하고 벨만 - 포드 알고리즘을 사용한다. 이 접근법이 눈부신 실패를하는 이유를 설명하십시오. 다음은
private void findShortestPath(int src) {
queue.add(src);
distTo[src] = 0;
edgeTo[src] = -1;
while (!queue.isEmpty()) {
int v = queue.poll();
onQueue[v] = false;
for (Edge e : adj(v)){
int w = e.dest;
if (distTo[w] > distTo[v] + e.weight) {
distTo[w] = distTo[v] + e.weight;
edgeTo[w] = v;
}
if (!onQueue[w]) {
onQueue[w] = true;
queue.add(w);
}
//Find if a negative cycle exists after every V passes
if (cost++ % V == 0) {
if (findNegativeCycle())
return;
}
}
}
}
가장자리를 반대 방향으로 두 개의 가장자리로 변환함으로써 새로운 부정적인 사이클을 만들 수 있습니다. 가중치가있는 undirected edge-weighted 그래프에는 기존의 음수 사이클이 없다고 가정합니다.
Offtopic. 프로그래밍 문제가 아닙니다. 이것은 CS 이론입니다. http://cs.stackexchange.com을 시도하십시오 –
OP가 CS 이론에 교차 게시 되었기 때문에이 질문을 주제와 관련이 없도록 닫으려고합니다. –
@MarcB 질문 : "BF를 유향 그래프로 작업하도록 구현했습니다. 각 모서리를 복사하여 두 방향으로 모두 이동시켜 방향이없는 그래프의 최단 경로를 찾을 수 있습니까?" 이것은 기본적으로 같은 질문이며 명확한 프로그래밍 컨텍스트와 주제가 분명합니다. (주어진 링크는 자바에서 구현을 제공한다) – amit