주어진 매개 변수를 사용하여 Graph에서 두 정점 간의 최단 경로를 계산하는 방법은 무엇입니까?

Question

우리 파라미터 follwing을 한 minCost()을 계산할 필요가 없다 :

1. gNodes - 노드의 어떠한 그래프 g이다.
2. int의 배열 gFrom 여기서 gfrom [i]는 그래프 g에서 ith 에지로 연결된 노드를 나타냅니다.
3. int의 배열 gTo 여기서 gTo [i]는 그래프 g에서 ith edge로 연결된 노드를 나타냅니다.
4. g의 각 에지의 각 가중치를 나타내는 int 배열이 gWeight입니다.
5. int 시작 시작 노드 색인을 나타냅니다.
6. int, 끝, 끝 노드 인덱스를 나타냅니다.
7. 정수, wExtra, 선택적 여분 가장자리의 무게를 나타냅니다.

최소 가능한 무게를 가진 경로를 처음부터 끝까지 찾아야합니다. wExtra 무게 사이에 최대 하나의 여분의 가장자리 (즉, 0 또는 1)를 추가 할 수 있습니다. 가장자리에이 아직 연결되어 있지 않은 두 개의 별개 노드가 사이에 추가 될 수 있습니다. 이 함수는 처음부터 끝까지 최소 경로 가중치를 나타내는 int를 반환해야합니다.

다음 코드 (Dijkstra 알고리즘)를 생각해 낼 수는 있지만 예상되는 결과는 제공하지 않습니다.

public static int minCost(int gNodes, int[] gFrom, int[] gTo, int[] gWeights, int start, int end) { 
//making a array to store shortest length and filling it with infinity except the first one 
      int[] shortest = new int[gNodes]; 
      for (int i = 0; i < gNodes; i++) { 
       shortest[i] = Integer.MAX_VALUE; 
      } 
      shortest[start]=0; 
//filling the Queue with all vertices 
     Queue<Integer> theQ = new PriorityQueue<>(); 
     for (int i = 0; i < gNodes; i++) { 
      theQ.add(i + 1); 
     } 
//following the algorithm 
     while (!theQ.isEmpty()) { 
      int u = theQ.poll(); 
//making a list of adjacent vertices 

      List<Integer> adjacent = new ArrayList<>(); 
      for (int i = 0; i < gFrom.length; i++) { 
       if (gFrom[i] == u) { 
        adjacent.add(gTo[i]); 
       } else if (gTo[i] == u) { 
        adjacent.add(gFrom[i]); 
       } 
      } 
      for (int v: adjacent) { 
       int weight=0; 
       for (int i = 0; i < gFrom.length; i++) { 
        if ((gFrom[i] == u && gTo[i] == v) || (gFrom[i] == v && gTo[i] == u)) { 
         weight = gWeights[i]; 
        } 
       } 

//relaxing the verices 
       if (shortest[v] > shortest[u] + weight) { 
        shortest[v] = shortest[u] + weight; 
       } 
       if (v == end) { 
        return shortest[v]; 
       } 
       theQ.add(v); 
      } 
     } 
     return -1; 
    } 


    public static void main(String[] args) { 
     int gNodes = 4; 
     int[] gFrom = {1, 2, 2, 3}; 
     int[] gTo = {2, 3, 4, 4}; 
     int[] gWeights = {2, 1, 2, 3}; 
     int start =1; 
     int end = 4; 
     System.out.println(shortestDistance(gNodes, gFrom, gTo, gWeights, start, end)); 
    } 
} 

것은 내가 그 wExtra을 사용하는 방법을 생각할 수 없기 때문에 생각 예상 출력을 포기하지 않을거야. 또한이 코드는 상당히 엉망입니다. 무엇이 잘못 되었는 지 알려주거나 잘 수행 할 수있는 강력한 코드를 제공하십시오. 감사.

그래프 중복, 당신은 모든 입력 노드에 대해 두 개의 노드가되도록 : wExtra를 통합하는

Answer 1

가능한 아이디어는 다음이다. 원본 그래프는 새 가장자리를 도입하기 전의 상태를 나타냅니다. 사본은 소개 이후의 상태를 나타냅니다. 원래 그래프에있는 모든 노드 n에 대해, m의 원본이 n에 인접하지 않은 복사본의 모든 노드 m에 가중치가 wExtra 인 방향성 에지를 도입해야합니다. 이것은 기본적으로 두 인접하지 않은 모서리 사이에 새 모서리를 도입 할 수 있다는 사실을 나타냅니다. 하지만 일단이 일을 마치면 돌아갈 수 없습니다. 그런 다음 수정 된 그래프에서 보통 Dijkstra를 start과 end 또는 end의 복사본으로 실행하십시오. 올바른 결과를 얻으실 수 있습니다.

이것을 시각화하는 가장 좋은 방법은 아마 두 개의 하위 그래프를 레이어로 해석하는 것입니다. 원래 레이어에서 시작하여 두 개의 end 노드 중 하나 (둘 중 더 가까운 쪽) 중 하나에 도달하려고합니다. 그러나 레이어를 한 번만 전환 할 수 있습니다.