가장 긴 경로에 대한 Dijkstra의 알고리즘

Question

EDIT 2 : 이것은 너무 늦었을 수도 있지만 문제를 파악했습니다. 나는 프로젝트를 오해했고, 가장 긴 경로가 아니라 가장 큰 대역폭 경로를 요구했다. 그것은 다르지만 지금까지는 알지 못했습니다. 기본적으로 모든 대역폭 경로 문제 (최대 또는 최소)에서 가중치는 누적되지 않으며 경로 값은 경로에서 가장 작은 가중치로 결정됩니다. 그것을 파이프의 경로라고 생각하면 물의 흐름은 경로를 따라가는 가장가는 파이프에 의해 결정됩니다.

편집 1 : PQ 문제가 수정되었지만 여전히 작동하지 않습니다.

과제 (인정)이지만 제출하지 않으면 전체 과정에 실패 할 수 있습니다. Dijkstra의 알고리즘을 수정하여 최단 경로 대신 가장 긴 단순 경로를 계산해야합니다. 해결책을 찾지 못했습니다. 나는 인터넷을 수색하고 this를 찾아 냈다 (그것은 동일한 문제조차이다).

하지만 실행하면 잘못된 값이 생성됩니다. 내가 빠진 것이 있습니까? 왜 전신과 무게를 합산하지 않습니까? 왜 분을 사용합니까?

그래프에 대한 정보 : 1. 각 노드가 다른 노드의 약 25 %에 대해 에 연결되도록 임의로 그래프를 생성합니다. 2. 무게는 양수입니다. 3. 그래프에 25 개의 노드가 있습니다.

"라우팅 알고리즘은 그래프에서 최대 대역폭 경로를 찾는 알고리즘으로 Max-Heap 구조를 사용하는 Dijkstra의 알고리즘 수정을 기반으로합니다"라고 말합니다. 도움이 될만한 트릭이 있습니까?

public class MaxDijkstra { 
    Graph graph; 
    PriorityQueue<Node> queue; 

    public MaxDijkstra(Graph graph, Node s){ 
     this.graph = graph; 
     s.addAttribute("ui.class", "start"); 
     queue = new PriorityQueue<>(new Comparator<Node>(){ 
      @Override 
      public int compare(Node n1, Node n2) { 
       if(Utils.getNodeBW(n1) == Utils.getNodeBW(n2)){ 
        return 0; 
       }else if(Utils.getNodeBW(n1) < Utils.getNodeBW(n2)){ 
        return 1; 
       }else{ 
        return -1; 
       } 
      } 
     }); 

     // init 
     for(Node n : graph){ 
      Utils.setNodeBW(n, 0); 
     } 
     Utils.setNodeBW(s, Float.POSITIVE_INFINITY); 

     // add to Q 
     for(Node n : graph){ 
      queue.add(n); 
     } 

     while(!queue.isEmpty()){ 
      Node u = queue.remove(); 
      Iterator<Node> iterator = u.getNeighborNodeIterator(); 
      while(iterator.hasNext()){ 
       Node v = iterator.next(); 
       float min = Float.min(Utils.getNodeBW(u), Utils.getEdgeBW(u.getEdgeBetween(v))); 
       if(min > Utils.getNodeBW(v)){ 
        Utils.setNodeBW(v, min); 
        Utils.setPreOfNode(v, u); 
       } 
      } 

      // validate PQ 
      // I know it is not good, just for debuggin now 
      // I will implemnt my own PQ later 
      List<Node> list = new ArrayList<>(); 
      while(!queue.isEmpty()){ 
       Node w = queue.remove(); 
       list.add(w); 
      } 
      for(Node w : list){ 
       queue.add(w); 
      } 
     } 
    } 

    public void printInfo(){ 
     for(Node n : graph){ 
      System.out.println("N="+n.getId()+" D="+Utils.getNodeBW(n)+" pre="+ (Utils.getPreOfNode(n) == null ? "NIL" : Utils.getPreOfNode(n).getId())); 
     } 
    } 

    /** 
    * Just to colourise the path 
    * @param target 
    */ 
    public void backtrack(Node target){ 
     target.addAttribute("ui.class", "end"); 
     Node currunt = target; 
     Node pre = Utils.getPreOfNode(currunt); 
     while(pre != null){ 
      currunt.getEdgeBetween(pre).addAttribute("ui.class", "route"); 
      currunt = pre; 
      pre = Utils.getPreOfNode(currunt); 
     } 
    } 

샘플 출력 :

사전에 여러분 모두 감사합니다.

Answer 1

Dijkstra의 알고리즘을 사용하여 가장 긴 단순 경로를 찾을 수 없습니다. 이 문제는 NP 하드입니다. 사실, 알려진 다항식 해결책은 없습니다.

그래프가 비교적 작 으면 동적 프로그래밍을 사용하여 O(2^n * poly(n)) 솔루션을 얻을 수 있습니다.이 상태는 n ~ 20-30에 적합합니다 (상태는 방문한 정점과 마지막 정점의 마스크입니다.) 전환은 하나의 정점을 추가합니다 그것이 가능하다면).

그래프가 큰 경우 로컬 최적화 기술과 결합 된 다양한 추론 및 근사를 사용하여 좋은 (그러나 반드시 최적 일 필요는 없음) 솔루션을 얻을 수 있습니다.

Answer 2

모든 가중치에 -1을 곱하여 모든 가중치를 음수로 만듭니다. 그런 다음 Floyd-Warshall 알고리즘을 사용할 수 있습니다. Floyd-Warshall 알고리즘은 사이클이없는 그래프에서 음수 가중치와 함께 작동합니다. Floyd-Warshall을 사용하여 가장 작은 경로를 찾으십시오. -1을 곱하면 원래 그래프의 최대 경로가됩니다.

Answer 3

우선 순위 대기열에 이미있는 요소는 변경할 수 없습니다. 일반적으로 Dijkstra에는 decrease key 함수가 필요하지만 라이브러리의 함수는이를 지원하지 않으므로 다른 BW 값으로 노드를 여러 번 pq에 다시 삽입 할 수 있습니다. 이와 비슷한 것 (의사 코드로 간주) :

PriorityQueue<pair<Node, int>> queue; 

    public MaxDijkstra(Graph graph, Node s){ 

     queue = new PriorityQueue<>(new Comparator<pair<Node, int>>(){ 
      @Override 
      public int compare(pair<Node, int> n1, pair<Node, int> n2) { 
       return n1.second > n2.second; 
      } 
     }); 

     // init 
     for(Node n : graph){ 
      Utils.setNodeBW(n, 0); 
     } 
     Utils.setNodeBW(s, Integer.MAX_VALUE); 

     // add to Q 
     for(Node n : graph){ 
      queue.add({n, n.getNodeBW()}); 
     } 

     while(!queue.isEmpty()){ 
      pair<Node, int> u = queue.remove(); 
      if (u.second < u.first.getNodeBW()) continue; //important - skip if you already saw better value 
      Iterator<Node> iterator = u.getNeighborNodeIterator(); 
      while(iterator.hasNext()){ 
       Node v = iterator.next(); 
       int min = Integer.min(Utils.getNodeBW(u), Utils.getEdgeBW(u.getEdgeBetween(v))); 
       if(min > Utils.getNodeBW(v)){ 
        Utils.setNodeBW(v, min); 
        queue.insert({v, min}); 
       } 
      } 
     } 
    } 
}