-2

我们提供了一个无向图、源节点、目标节点和额外边的权重，您可以使用它来连接之前未连接的任何两个节点。您必须找到源和目的地之间可能的路径的最小权重。您只能使用提供的边缘一次。这是一个示例：具有 5 条边的图形如下 1->2 权重为 1,2->3 权重为 2,3->4 权重为 3,4->5 权重为 1,1- >4 权重为 3，源顶点为顶点 1，目的地为顶点 4。我们必须告诉最小路径长度。（在这种情况下是 2）我们可以使用添加一个额外的权重边缘 1（这里从 1 到 5 ）我想知道如何在 java 中实现它。

4

2 回答 2

0

如果我正确理解了这个问题，那么您正在寻找的只是 java 中广度优先搜索的实现，可以在这里找到。除非您使用额外的边缘在 1 和 4 之间创建直接路径（即源和目标），否则我认为额外的边缘权重没有任何用处（因为这只会增加距离），因此最短的距离会变为 1。但同样，您必须在每种情况下检查此额外边的权重是否小于广度优先搜索所获得的权重。此外，在不使用额外边的情况下，在这种情况下最短距离是 3，而不是 2。

于 2016-10-24T09:45:28.327 回答
0

假设您没有零边缘和负边缘。您将边保留在数组 a[N][N] 中。稍微修改一下图表：

  • 从源图生成有向图 A：

    for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        if (a[i][j] > 0 && a[j][i] == 0)
            a[j][i] = a[i][j];

  • 制作图的副本并添加野边（野边是定向的，从 A 部分引导到 B 部分，具有预定义的权重）

  • 定义数组b：int b[2*N][2*N]，用零初始化边

    for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        if (a[i][j] == 0) {
            b[i][N+j] = wildWeight;
        } else {
            b[i][j] = a[i][j];
            b[N+i][N+j] = a[i][j];
        }

谷歌在 java 中的 Dijkstra 算法实现，并在该 midified 图上使用它。

于 2016-10-24T10:16:46.080 回答