在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路径寻找解决方案中寻找路径和最大称量的边缘？

回答

相关问题