贝尔曼福特性能

Question

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

我已经从 (LinkedList) 的列表中实现了 bellman ford，因为该算法运行 V-1（循环 1）次并进入每个顶点（在循环 2 中）它检查所有边（在循环 3 中）并更新destinations.I 的距离在这里很困惑，时间复杂度仍然是 O(VE) 或发生了变化，我已经看到这项工作在 2 个循环中完成，这就是为什么，并且还会为经过的每个顶点找到最短路径或者我必须从 0 开始？

Answer 1

就您检查 V 时间的所有边而言，复杂度仍然是 O(VE)。欲了解更多信息，请阅读 this。

贝尔曼福特性能

Bellman ford performance

java

performance

shortest-path

data-structures

bellman-ford