Ford-Bellman algorithm-path recovery

The course program requires a software implementation of this algorithm. But I'm stuck at the stage of restoring the path along the vertices, please help me.

static final double INF = Double.POSITIVE_INFINITY;

public static void BellmanFord(double[][] z, int start, int end) {
    int verticesCount = z.length;

    double[] q = new double[verticesCount];
    ArrayList<Double> labels = new ArrayList<>();

    for (int i = 0; i < verticesCount; i++) {
        q[i] = INF;
    }

    q[start - 1] = 0.0;

    for (int k = 0; k <= verticesCount - 1; k++) {
        for (int i = 0; i < verticesCount; i++) {
            for (int j = 0; j < verticesCount; j++) {
                labels.add(q[j] + z[j][i]);

            }
            q[i] = minOfArray(labels);
            labels.clear();
        }
    }
    System.out.println(q[end - 1]);
}

public static double minOfArray(ArrayList<Double> array) {
    double min = INF;
    for (int i = 0; i < array.size(); i++) {
        if (min > array.get(i))
            min = array.get(i);
    }
    return min;
}
Author: Юлия, 2020-12-20

1 answers

When the if (min > array.get(i)) condition is triggered, write the i number (local i of the minOfArray function to the additional list preds!!) the best ancestor for the vertex i (local i of the cycle for (int i = 0; i < verticesCount; i++)).

At the end of the work, to find the path to the vertex q, take its ancestor preds[q], then its ancestor, and so unwind to the initial vertex

 0
Author: MBo, 2020-12-21 07:35:50