在Minimax路径寻找解决方案中找到路径和最大权重边缘？-Java 学习之路

我目前正在编程分配：给定一个大的加权未连接图（1 <V <2000,0 <E <100 000） . 找到沿“最小加权路径”从“源”到“目标”的最大加权边 .

到目前为止我所拥有的是将图存储在AdjacencyList中（IntegerPair的Vector of Vector，其中第一个整数是邻居，第二个是边的权重） .

我还使用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将遍历所有不在正确路径上的顶点（我是对的吗？） . 以及如何找到最大边缘？

（这个问题与任何SSSP算法无关，因为我没有被教过Dijstra等等）

1 回答

0

一种可能的方法是使用Kruskal的MST算法 . 这是一个贪婪的算法，将以空图开始，重复添加不产生循环的最轻边 . 这满足树的属性，同时确保最小加权路径 .

要查找最大加权边，您还可以使用算法的属性 . 由于您知道EdgeWeight（n）= <EdgeWeight（n 1），因此添加到图形的最后一条边将是最大边 .

回复于 2024-05-05T10:32:10+08:00

在Minimax路径寻找解决方案中找到路径和最大权重边缘？

1 回答

相关问题