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;
}
1
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