2016-08-23 12 views
1

Algorithms, 4th edition, Robert Sedgewick and Kevin Wayne에서 아래의 문제가 발생했을 때 최단 경로 알고리즘을 가장 최근에 알고있었습니다.Bellman Ford 알고리즘이 방향성 가중 그래프의 최단 경로를 계산하지 못했습니다.

는 EdgeWeightedGraph의 각 에지에 대해 EdgeWeightedDigraph (각 방향으로 하나)의 두 DirectedEdge 객체를 생성하여 우리가 방향성 EdgeWeightedGraph 내로 EdgeWeightedGraph 변환한다고 가정하고 벨만 - 포드 알고리즘을 사용한다. 이 접근법이 눈부신 실패를하는 이유를 설명하십시오. 다음은

는 조각 내 code 구현 벨만 포드 알고리즘 (큐 기반) : 나는 종이에 많은 예를하려고했으나 방향 그래프가 생성 시나리오를 찾을 수없는 생각했습니다

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 그래프에는 기존의 음수 사이클이 없다고 가정합니다.

+0

Offtopic. 프로그래밍 문제가 아닙니다. 이것은 CS 이론입니다. http://cs.stackexchange.com을 시도하십시오 –

+0

OP가 CS 이론에 교차 게시 되었기 때문에이 질문을 주제와 관련이 없도록 닫으려고합니다. –

+2

@MarcB 질문 : "BF를 유향 그래프로 작업하도록 구현했습니다. 각 모서리를 복사하여 두 방향으로 모두 이동시켜 방향이없는 그래프의 최단 경로를 찾을 수 있습니까?" 이것은 기본적으로 같은 질문이며 명확한 프로그래밍 컨텍스트와 주제가 분명합니다. (주어진 링크는 자바에서 구현을 제공한다) – amit

답변

-1

당신의 알고리즘 & 코드는 아무런 문제가 없습니다. 음의 원이없는 그래프에서 최단 거리를 줄 수 있습니다. 그리고 'number [i]'배열로 음의 원을 쉽게 찾을 수 있습니다. 'i '가 대기열에 넣어집니다.

이 입증 될 수있는 점은 이상을 위해 대기열에 넣을 경우 | P | (지점 수) 시간, 당신은 추가 할 수 graph.So에 부정적인 원이 :

number[v]++; if (number[v] > |P|) return -1;

네거티브 원이있는 그래프의 최단 거리는 의미가 없습니다. 대부분의 상황에서 찾을 때 뭔가를 인쇄하면됩니다.

+0

안녕하세요. 귀하의 대답은 내가 게시 한 질문과 관련이 없습니다. 응답하는 동안 http://meta.stackexchange.com/questions/7656/how-do-i-write-a-good-answer-to-a-question에서 설정된 지침을 따르십시오. –

+0

미안하지만, 나는 영어로 가난하다. 그러나 나는 방향이없는 그래프에 음의 가장자리가 있으면 음의 원이라고 생각한다. 부정적인 원의 정의는 "길을 시작하고 음수 길이 ". 왼쪽에서 오른쪽으로 왼쪽으로 갈 수 있습니다 ... 가장자리에서 알고리즘이 작동하지 않습니다. 한 번만 사용하면 한 번만 사용하도록 정의하면 알고리즘이 또 하나 있습니다. 받아 들여. – ljt12138

+0

고마워요. 이 시점에서 답을 편집하면 수락 할 수 있습니다. –