Minimax 경로 찾기 솔루션에서 경로와 최대 무게 가장자리를 찾으시겠습니까?

Question

현재 큰 할당되지 않은 연결되지 않은 그래프 (1 < V < 2000, E < 100 000)이 주어졌습니다. "source"에서 "destination"을 가리키는 최소 가중 경로를 따라 최대 가중 에지를 찾습니다.

내가 지금까지 가지고있는 것은 AdjacencyList (Vector는 IntegerPair의 Vector이며 첫 번째 정수는 이웃이고 두 번째는 가장자리의 무게 임)에 그래프를 저장하는 것입니다.

는 또한 프림의 알고리즘을 사용하여 최소 스패닝 트리를 획득했습니다

private static void process(int vtx) { 
    taken.set(vtx, true); 

    for (int j = 0; j < AdjList.get(vtx).size(); j++) { 
     IntegerPair v = AdjList.get(vtx).get(j); 
     if (!taken.get(v.first())) { 
      pq.offer(new IntegerPair(v.second(), v.first())); //sort by weight then by adjacent vertex 
     } 
    } 
} 

void PreProcess() { 
    Visited = new Vector<Boolean>(); 
    taken = new Vector<Boolean>(); 
    pq = new PriorityQueue<IntegerPair>(); 

    taken.addAll(Collections.nCopies(V, false)); 

    process(0); 
    int numTaken = 1; 
    int mst_cost = 0; 

    while (!pq.isEmpty() && numTaken != V) { //do this until all V vertices are taken (or E = V - 1 edges are taken) 
     IntegerPair front = pq.poll(); 

     if (!taken.get(front.second())) { // we have not connected this vertex yet 
      mst_cost += front.first(); // add the weight of this edge 
      process(front.second()); 
      numTaken++; 
     } 
    } 
} 

지금에 붙어있는 무슨 원본에서 대상으로 경로를 찾아 아래에 maxmum 무게 가장자리를 반환하는 방법입니다 질의 : 내가 깊이 우선 검색을 사용 들었다

int Query(int source, int destination) { 
int ans = 0; 



return ans; 
} 

이 결과 MST를 통과 할 수 있지만이 DFS가 올바른 경로에없는 모든 정점을 통과 생각 (내가 맞다?). 그리고 최대 가장자리를 찾는 방법? 크루스 칼의 MST 알고리즘을 사용하는 것이 작업을 수행하는

Answer 1

한 가지 가능한 방법을

은 (내가 Dijstra의 등을 가르쳐되지 않았기 때문에이 문제는 어떤 SSSP 알고리즘 관련이 없습니다). 빈 그래프로 시작하는 욕심 많은 알고리즘이며, 이 아닌 가장 가벼운 가장자리를 반복적으로 추가하면 사이클이 생성됩니다. 이것은 최소 가중 경로를 보장하면서 트리의 속성을 만족시킵니다.

최대 가중 에지를 찾으려면 알고리즘의 속성을 사용할 수도 있습니다. EdgeWeight (n) = < EdgeWeight (n + 1)을 알고 있기 때문에 그래프에 마지막으로 추가 한 가장자리가 최대 가장자리가됩니다.