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

首先，我的 Graph 包含负权重，所以我不能使用 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其中I必须计算的最短路径）。所以，在这个输入文件中，我的代码给了我这个输出，如果我们看到我为你做的画，那就错了。

虽然输出是：

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) （它与第一个类似，但在最后一个 raw 中权重不同）：

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

The only thing I know is that for the first input the output should be -1, while for the last input the output should be 2 -> 1 -> 3 which is the path with the shortest distance between a source node and a destination node (and it's correct).

Thank you