Найдите путь и максимальную привязку в решении поиска Minimax?

Question

В настоящее время у меня есть программирующее назначение: с учетом большого взвешенного несвязанного графика (1 < V < 2000, E < 100 000). Найдите максимальный взвешенный край вдоль минимально взвешенного пути от «источника» до точки «пункт назначения».

Что я до сих пор храню в графе AdjacencyList (Vector of Vector IntegerPair, где первое целое является соседним, а второе - весом ребра).

Я также получил минимального остова с помощью алгоритма Прима:

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 будет пересекать все вершины, которые не на правильном пути (я прав?). И как найти максимальный край?

(Эта проблема не связана с какой-либо SSSP алгоритма, потому что я не учил Dijstra-х и т.д.)

Answer 1

Одним из возможных способов сделать это было бы использовать алгоритм MST Крускала. Это жадный алгоритм, который начнется с пустого графа, повторно добавьте самый легкий край, который делает не производят цикл. Это удовлетворяет свойствам дерева, гарантируя минимально-взвешенный путь.

Чтобы найти максимальный взвешенный край, вы также можете использовать свойства алгоритма. Поскольку вы знаете, что EdgeWeight (n) = < EdgeWeight (n + 1), последний край, который вы добавляете на график, будет максимальным краем.