Skip to main content

Bellman-Ford algorithm

Bellman-Ford

Bellman-Ford

Bellman-Ford vs. Dijkstra

  • Dijkstra's algorithm:

    • find the u with the smallest d[u]
    • Update u's neighbors: d[v] = min(d[v], d[u] + w(u, v))

  • Bellman-Ford algorithm:

    • Don't bother finding the u with the smallest d[u]
    • Slower, but more robust than Dijkstra's algorithm
      • Can handle negative edge weights (as long as there are no negative cycles)
      • Can do updates in a decentralized setting

Bellman-Ford algorithm

  • Initialize d[s] = 0, d[v] = +∞ for all v ≠ s
  • for i = 0 to n-2:
    • for each edge (u, v) ∈ E:
      • d(i+1)d^{(i+1)}[v] = min( d(i)d^{(i)}, d(i)d^{(i)} + w(u, v))
  • Now dist(s,v) = d[v] for all v ∈ V

d(i)[v]d^{(i)}[v] = length of shortest path from s to v using at most i edges.

Correctness of Bellman-Ford

  • Claim: After i iterations, d(i)[v]d^{(i)}[v] = length of shortest path from s to v using at most i edges.
  • Proof: By induction on i.
    • Base case: i = 0
      • d(0)[s]d^{(0)}[s] = 0
      • d(0)[v]d^{(0)}[v] = +∞ for all v ≠ s
    • Inductive step: i > 0
      • Consider any edge (u, v) ∈ E
      • d(i)[v]d^{(i)}[v] = min( d(i−1)d^{(i-1)}, d(i−1)d^{(i-1)} + w(u, v))
      • By induction, d(i−1)[u]d^{(i-1)}[u] = length of shortest path from s to u using at most i-1 edges
      • So d(i)[v]d^{(i)}[v] = length of shortest path from s to v using at most i edges

Simple path

Assume there is not negative cycle.

  • Then there is a shortest path from s to t, and moreover there is a simple shortest path from s to t.
  • A simple path is a path with no repeated vertices.

What is dynamic programming?

  • A way of solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.

  • Usually it is for solving optimization problems.

Elements of dynamic programiong:

  • optimal substructure

    • optimal solution to the problem contains within it optimal solutions to subproblems

  • overlapping subproblems

    • subproblems recur many times, this means that we can save time by solving a sub-problem just onece and storing the answer.

Two ways to implement dynamic programming:

  • Bottom up approach

    • solve the small sub-problems first, then use the solutions to solve larger sub-problems until the entire problem is solved.

  • Top down approach

    • start with the original problem, and recursively break it down into subproblems.
    • Keep track of what small problems you've already solved so that you don't waste time solving the same problem twice.

Floyd-Warshall algorithm

  • This is an algorithm for all-pairs shortest paths (APSP).

Naive algorithm:

  • Run Bellman-Ford n times, once for each vertex as the source vertex.
  • This takes O(n×nm)=O(nm2)O(n \times nm) = O(nm^2) time.

Optimal substructure:

  • Sub-problem(k-1): shortest path from i to j using only vertices in {1, 2, ..., k-1} as intermediate vertices.

  • Sub-problem(k): shortest path from i to j using only vertices in {1, 2, ..., k} as intermediate vertices.

    • Case 1: Don't need vertex k, D(k)[u,v]=D(k−1)[u,v]D^{(k)}[u,v] = D^{(k-1)}[u,v]
    • Case 2: Need vertex k, D(k)[u,v]=D(k−1)[u,k]+D(k−1)[k,v]D^{(k)}[u,v] = D^{(k-1)}[u,k] + D^{(k-1)}[k,v]
    • D(k)[u,v]=min(D(k−1)[u,v],D(k−1)[u,k]+D(k−1)[k,v])D^{(k)}[u,v] = min(D^{(k-1)}[u,v], D^{(k-1)}[u,k] + D^{(k-1)}[k,v])

Floyd-Warshall algorithm:

  • Initialize n-by-n arrays DkD^{k} for k = 0, 1, ..., n

    • D(0)[u,v]=∞D^{(0)}[u,v] = \infty for all pairs u, v
    • D(0)[u,u]=0D^{(0)}[u,u] = 0 for all u
    • D(0)[u,v]=w(u,v)D^{(0)}[u,v] = w(u,v) if (u,v) ∈ E

  • for k = 1 to n:

    • for pairs u,v in V:
      • D(k)[u,v]=min(D(k−1)[u,v],D(k−1)[u,k]+D(k−1)[k,v])D^{(k)}[u,v] = min(D^{(k-1)}[u,v], D^{(k-1)}[u,k] + D^{(k-1)}[k,v])

  • Now D(n)[u,v]D^{(n)}[u,v] = length of shortest path from u to v

Running time: O(n3)O(n^3) Space: O(n2)O(n^2)

Comments

Post a Comment

Popular posts from this blog

Tries

Tries Tries Tries and Patricia Tries Motivation: The autocomplete feature in a text editor. We have a dictionary of words, and we want to find all the words that start with a given prefix. The data structure we use to store the dictionary is called a trie. Each edge is labeled with a character. Some nodes are marked as terminal nodes. By convention, children of a node are ordered alphabetically. A preordering traversal of the trie yields the words in the dictionary in alphabetical order. The total length of our text strings is m and the length of our pattern string is n . Time to build the trie: O(m) Time to search for a pattern: O(n) How long does it take to find all the words that start with a given prefix? The $ symbol is called the sentinel or marker, add this to the end of each word. It is used to mark the end of a word, it precedes all other characters in the alphabet....
Post a Comment
Read more

Recap on BFS, DFS and Strongly Connected Components

graph graph DFS topological sort considering the dependencies between tasks, we can use topological sort to find the order of tasks. def topological_sort ( graph ): visited = set () stack = [] for node in graph: if node not in visited: dfs(graph, node, visited, stack) return stack[::- 1 ] def dfs ( graph, node, visited, stack ): visited.add(node) for neighbor in graph[node]: if neighbor not in visited: dfs(graph, neighbor, visited, stack) stack.append(node) if A -> B then B.finishtime < A.finishtime, that's why we need to reverse the stack. Topological Sorting on a DAG do DFS on the graph when a node is finished, insert it into the front of a linked list Another use of DFS is in-order traversal of a binary tree . BFS BFS is used to find the shortest path in an unweighted graph . we can...
Post a Comment
Read more

Balanced Trees

Balanced Trees Balanced Trees Balanced search trees are among the most useful and versatile data structures. Many programming languages include balanced search trees in their standard libraries. e.g. C++: std::map , Java: TreeMap , Python: dict , etc. Many advanced data structures are layered on top of balanced search trees.. A quick BST recap A binary search tree is a binary tree where each node has a key and a value, and the following properties hold: Each node in the BST stores a key, and optinally, some information associated with the key. The keys in the left subtree are less than the key in its parent node, and the keys in the right subtree are greater than the key in its parent node. The height of a BST is the number of nodes on the longest path from the root to a leaf. A tree with one node has height 0, A tree with no nodes has height -1. Deleting from a BST Deleting a n...
Post a Comment
Read more