java - 从源列表和目的地列表中找到有向加权图中的最短路径

Question

首先是我的图表包含负权重，所以我不能使用 Dijkstra 算法。

我尝试使用和编辑一种 Floyd-Warshall 算法，但它只在某些情况下有用。也许我必须使用 Bellman-Ford 算法的编辑版本，但我找不到办法......

<EDIT>

我无法找到获得正确输出的方法，不是因为我能够找到最短路径，而是在此输入中获得正确的输出。 (看图和输出比较，可以看出不一样。例如:

2 -> 5     -4    2 -> 1 -> 3 -> 4 -> 5

距离 -4 不正确，在绘图中是 -2，而在另一个输入有点不同的输出中，如下文所述，一切都是正确的。

</EDIT>

这是我的输入 (1) 文件:

6 9
2 3
0 1 -2
0 2 1
2 1 -3
1 3 2
2 3 3
2 5 1
5 3 1
3 4 1
4 5 -3

在哪里6是节点数，9是边数，2和 3分别是我必须计算最短路径的源和目的地( 0<=sourceNodes<=2 和 3<=destinationsNodes<=5 )。因此，在这个输入文件中，我的代码为我提供了这个输出，如果我们看到我为您绘制的图，那就错了。

虽然输出是:

pairs     dist     path
0 -> 3    -1     0 -> 1 -> 3
0 -> 4     0     0 -> 1 -> 3 -> 4
0 -> 5    -3     0 -> 1 -> 3 -> 4 -> 5
1 -> 3     1     1 -> 3
1 -> 4     2     1 -> 3 -> 4
1 -> 5    -1     1 -> 3 -> 4 -> 5
2 -> 3    -2     2 -> 1 -> 3
2 -> 4    -1     2 -> 1 -> 3 -> 4
2 -> 5    -4     2 -> 1 -> 3 -> 4 -> 5

这是我的代码:

import java.util.*;
import java.lang.*;
import java.io.*;

public class Esercizio3 {

public static void main(String args[]) throws IOException {
    try {
        Scanner scan = new Scanner(new File("/myFiles/Input2Es3.txt"));
        int totNodi = scan.nextInt();
        System.out.println("totNodi: "+totNodi);
        int totArchi = scan.nextInt();
        System.out.println("totArchi: "+totArchi);
        // ingressi
        int nIngressi = scan.nextInt();
        System.out.println("nIngressi: "+nIngressi);
        int[] ingresso = new int[nIngressi+1];
        for (int i=0; i<=nIngressi; i++) {
            ingresso[i] = i;
            System.out.println("> INGRESSO: "+ingresso[i]);
        }
        // uscite
        int startUscite = scan.nextInt();
        //        int endUscite = totNodi-1;
        int nUscite = totNodi-startUscite;
        System.out.println("nUscite: "+nUscite);
        int[] uscita = new int[nUscite];
        for (int i=startUscite; i<totNodi; i++) {
            int index = i-startUscite;
            uscita[index] = i;
            System.out.println("> USCITA: "+uscita[index]);
        }
        // archi
        int V = totNodi;
        int E = totArchi;
        int[][] weights = new int[totArchi][3];
        for (int i=0; i<totArchi; i++) {
            weights[i][0] = scan.nextInt();
            weights[i][1] = scan.nextInt();
            weights[i][2] = scan.nextInt();
            System.out.println(weights[i][0] + " - " + weights[i][1] + " - " + weights[i][2]);
        }

        floydWarshall(weights,totNodi,ingresso,uscita);


    } catch (FileNotFoundException ex) {
        System.out.println(ex);
    }
}

static void floydWarshall(int[][] weights, int numVertices, int[] ingresso, int[] uscita) throws IOException {

    double[][] dist = new double[numVertices][numVertices];
    for (double[] row : dist)
        Arrays.fill(row, Double.POSITIVE_INFINITY);

    for (int[] w : weights)
        dist[w[0]][w[1]] = w[2];

    int[][] next = new int[numVertices][numVertices];
    for (int i = 0; i < next.length; i++) {
        for (int j = 0; j < next.length; j++)
            if (i != j)
                next[i][j] = j + 1;
    }

    for (int k = 0; k < numVertices; k++)
        for (int i = 0; i < numVertices; i++)
            for (int j = 0; j < numVertices; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];
                }

    printResult(dist, next, ingresso, uscita);
}

static void printResult(double[][] dist, int[][] next, int[] ingresso, int[] uscita) throws IOException {
    BufferedWriter writer = new BufferedWriter(new FileWriter("myoutputfile.txt"));

    double distMin =  Double.POSITIVE_INFINITY;
    int indexI = 0;
    int indexJ = 0;
    for (int i = 0; i < next.length; i++) {
        for (int j = 0; j < next.length; j++) {
            if ((i != j) && (dist[i][j]!=Double.POSITIVE_INFINITY) && (i>=ingresso[0] && i<=ingresso[ingresso.length-1]) && (j>=uscita[0] && j<=uscita[uscita.length-1])) {
                int u = i + 1;
                int v = j + 1;
                String path = format("%d -> %d    %2d     %s", i, j, (int) dist[i][j], i);
                do {
                    u = next[u-1][v-1];
                    path += " -> " + (u-1);
                } while (u != v);
                System.out.println(path);



                if(distMin > dist[i][j]) {
                    distMin = dist[i][j];
                }

            }
        }
    }
}

}

我该如何解决这个问题？因为使用另一个输入它可以完美运行:

输入 (2) 运行 (它与第一个相似，但最后一个原始权重不同):

6 9
2 3
0 1 -2
0 2 1
2 1 -3
1 3 2
2 3 3
2 5 1
5 3 1
3 4 1
4 5 1

输出完美:

0 -> 3     0     0 -> 1 -> 3
0 -> 4     1     0 -> 1 -> 3 -> 4
0 -> 5     2     0 -> 2 -> 5
1 -> 3     2     1 -> 3
1 -> 4     3     1 -> 3 -> 4
1 -> 5     4     1 -> 3 -> 4 -> 5
2 -> 3    -1     2 -> 1 -> 3
2 -> 4     0     2 -> 1 -> 3 -> 4
2 -> 5     1     2 -> 5

我唯一知道的是第一个输入的输出应该是-1 , 而对于最后一个输入，输出应该是 2 -> 1 -> 3这是源节点和目标节点之间距离最短的路径(正确)。

谢谢

Answer 1

首先，如果存在负循环，那么我们就无法找到最短路径。很容易想象这一点。因为如果我们反复遍历负循环，那么每次遍历的成本都会降低。结果，我们会发现路径的值(value)会无限降低。

好吧，为了避免这个缺点，我们使用 Bellman-Ford 算法。它检测图形是否包含负循环。我假设您知道 Bellman-Ford 和 Dijkstra 的算法并且习惯使用术语“松弛”。

现在我们将遵循一种称为 Johnson 算法的方法:

• 我们将添加一个额外的顶点 X 并将其连接到图中的所有其他顶点，并且所有边的成本都将为 0。

• 以新顶点 X 为源，我们将应用 Bellman-Ford 的算法。它将找到所有边缘的最短路径总共 (n-1) 次迭代中的源，其中 n 是总次数包括 X 在内的顶点。我们将从相同的来源进行额外的迭代，它在两种不同的情况下会有不同的表现。

  1. 存在负循环:放松将再次发生。这意味着有一个负循环，我们不能有最短的正如我上面解释的那样，图中的路径。所以，我们的程序应该终止。

  2. 不存在负循环:不会发生松弛，我们得到了从 X 开始的所有顶点的最短路径。我们准备好了!

• 我们将使用 Bellman-Ford 算法中的最短路径对原始图的边重新加权。如果 u 和 v 在主图中有一条边，成本为 w(u,v) 并且 u 的最短路径> 和 X 中的 v 分别是 h(u) 和 h(v)，然后新的权重 nw(u,v) = w(u,v)+h(u)-h(v)。

现在，您选择的源中的 Dijkstra 算法应该找到到重新加权图上所有顶点的最短路径，这也是原始图的最短路径。

如果您仍然感到困惑，请查看 Johnson's algorithm在维基百科。