for(int k=1; k<=Vertices-1; k++){
/*Every sublist has found the shortest to its adjacent vertices
thats why starting loop from k-1 then going into every edge of a vertex
and updating the shortest distance from it to the other.
*/
for(int i=k-1; i<Vertices; i++){
// Visiting every Vertex(V) and checking distance of its edges to some other vertex Vo.
for(int j=0; j<Edges[i].size(); j++){
int v = Edges[i].get(j).src;
int edge = Edges[i].get(j).dest;
int weight = Edges[i].get(j).weight;
// if exisiting distance is not infinity and from source to that vertex the weight is less then update it
if (dist[v]!=Integer.MAX_VALUE && dist[v]+weight<dist[edge]){
dist[edge]=dist[v]+weight;
//updating parent of destination to source.
parent[edge] = v;
}
}
}
}
Я реализовал bellman ford из списка (LinkedList), поскольку алгоритм запускает V-1 (цикл 1) раз и, заходя в каждую вершину (в цикле 2), проверяет все его ребра (в цикле 3) и обновляет расстояния пунктов назначения. Я Меня здесь смущает, что временная сложность по-прежнему будет O (VE) или изменена, я видел, как эта работа выполняется в 2 цикла, поэтому, а также будет ли найден кратчайший путь для каждой проходящей вершины, или я должен начать его с 0?
