Bellman-Ford Algorithm

choikh0423·2022년 5월 15일
0

Graph Algorithm

목록 보기
1/2
post-thumbnail

What is Bellman-Ford Algorithm?

Bellman-ford algorithm will find the shortest path to all of the vertices from the source node.

Dijkstra's shortest path algorithm can not work around graphs with negative weight. Bellman-ford can.


Analysis

Time Complexity:
Generally:
O(E(V1))O(|E|(|V|-1)) which is O(EV)O(|E||V|)

Worst Case: graph is a complete graph
E=n(n1)2=n2n2O(n2)|E| = {n(n-1) \over 2} = {n^2-n \over 2} {\displaystyle \approx } O(n^2)
Therefore,
O(EV)=O(V2V)O(V3)O(|E||V|)=O(|V^2||V|){\displaystyle \approx }O(|V^3|)

Space Complexity:
O(V)O(|V|)

Conclusion:
If we were to say the number of verticies is nn. At worst case,

  • Time Complexity: O(n3)O(n^3)
  • Space Complexity: O(n)O(n)

Evaluation

Advantages

  • Can be applied to graphs w/ negative weight

Disadvantages

  • As Dijkstra's is greedy and Bellman-Ford is dynamic, it is slower than Dijkstra's.
  • Does not work if there is a negative cycle in the graph. We can find out if there is a negative cycle, but not work through it.

Implementation

1) Initialize dist list with length of n with float("inf")float("inf")
2) We will relax the graph n-1 times

  • Go through each edge to check if dist[v]>dist[u]+wdist[v] > dist[u] + w where uu will be the source node and vv will be the target node of that edge.
  • If dist[v]>dist[u]+wdist[v] > dist[u] + w update dist[v]=dist[u]+wdist[v] = dist[u] + w

3) If necessary: We will relax the graph one more time making it relaxed n times. If the values of dist for any nodes change on the nth relaxation, the graph contains negative cycle.


Code

def bellmanFord(self, times: List[List[int]], n: int, k: int) -> int:
    # Initializing dist list with float("inf")
    dist = [float("inf")] * (n)
    dist[k-1] = 0


    # Relaxation
    for _ in range(n-1):
        for u,v,w in times:
            # Updating shortest path to target node
            if dist[u-1] != float("inf") and dist[u-1] + w < dist[v-1]:
                dist[v-1] = dist[u-1] + w

    
    # Checking if there are unreached nodes
    if float("inf") in dist:
        return -1
    else:
        return max(dist)

0개의 댓글