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

Question

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

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

<EDIT>

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

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

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

</EDIT>

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

其中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) 运行 （它与第一个相似，但最后一个原始权重不同）:

输出完美：

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

你想尽可能地减少路线的总成本（-6 的结果比 -3 好）还是尽可能接近 0（-3 比 -6 好）？如果你试图接近 0，我认为这实际上可能是 NP-hard problem, where there is no reasonable algorithm, that will give you 100% correct answer. These kind of problems are usually solved either by some heuristic algorithms, that can get you good enough result or if the network of nodes is not that big, you can do enumeration with selecting the best one (writing this network as a linear programming problem，php、java ... 中有一些求解器可用于此。

Answer 2

我认为您可以使用经过改编的 Dijkstra。如果您在该循环中检测到导致负面结果的循环，则将路径标记为 "undefined"，因为最短路径是 "infinite short".

Answer 3

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

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

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

我们将添加一个额外的顶点 X 并将其连接到图中的所有其他顶点，所有边的成本都将为 0。
以新顶点X为源，我们将应用Bellman-Ford的算法。它将找到所有边缘的最短路径总共 (n-1) 次迭代中的源，其中 n 是总次数包括 X 在内的顶点。我们将从相同的来源进行额外的迭代，它在两种不同的情况下会有不同的表现。
1. 出现负循环：放松会再次发生。这意味着有一个负循环，我们不能有最短的正如我上面解释的那样，图中的路径。所以，我们的程序应该终止。
2. 不存在负循环：不会发生松弛，我们得到了从 X 开始的所有顶点的最短路径。我们准备好了！
我们将使用 Bellman-Ford 算法中的最短路径对原始图的边重新加权。如果 u 和 v 在主图中有一条边，成本为 w(u,v) 且最短来自 X 的 u 和 v 的路径是 h(u) 和 h( v)分别，然后新权重nw(u,v)=w(u,v)+h(u)-h(v)。

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

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

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

Find Shortest Path in a directed weighted graph from list of sources and list of destinations

java

algorithm

shortest-path