在Minimax路徑尋找解決方案中尋找路徑和最大稱量的邊緣？

我目前正在進行編程分配：給定大的加權無關圖（1 < V < 2000, E < 100000）。沿着從「源」到點「目的地」的最小加權路徑查找最大加權邊緣。在Minimax路徑尋找解決方案中尋找路徑和最大稱量的邊緣？

到目前爲止我所得到的是將圖存儲在AdjacencyList（IntegerPair向量的向量中，其中第一個整數是鄰居，第二個是邊的權重）。

我也用Prim算法獲得的最小生成樹：

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++; 
     } 
    } 
}

我停留在現在的是如何找到源路徑到目的地，並在下方返回的最大完全重邊緣查詢：

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



return ans; 
}

我被告知要使用深度優先搜索遍歷導致MST但我認爲DFS將穿越不在正確的路徑上的所有頂點（是嗎？）。以及如何找到最大優勢？

來源

2014-10-06 hydradon

這似乎與minimax沒有任何關係。 – 2014-10-06 19:44:31

一種可能的方式做到這一點是使用Kruskal的MST算法（因爲我沒有被教導Dijstra的，等等。這個問題是不相關的任何SSSP算法）。這是一個貪婪的算法，將開始一個空的圖形，重複添加最輕的邊緣，而不是產生一個循環。這滿足了樹的屬性，同時確保了最小加權路徑。

要找到最大加權邊緣，還可以使用算法的屬性。既然你知道EdgeWeight（n）= < EdgeWeight（n + 1），你添加到圖中的最後一條邊就是最大邊。

來源

2014-10-09 06:27:27 ianks

在Minimax路徑尋找解決方案中尋找路徑和最大稱量的邊緣？

回答

相關問題