0

我目前有一个编程任务：给定一个大的加权无连接图（1 < V < 2000, 0 < E < 100 000）。沿着从“源”到点“目的地”的最小加权路径找到最大加权边。

到目前为止，我将图形存储在 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 将遍历所有不在正确路径上的顶点（对吗？）。以及如何找到最大边缘？

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

4

1 回答 1

0

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

要找到最大加权边缘，您还可以使用算法的属性。由于您知道 EdgeWeight(n) =< EdgeWeight(n+1)，因此您添加到图中的最后一条边将是最大边。

于 2014-10-09T06:27:27.017 回答