Posted by: atri | December 11, 2009

## Lect 39: Bellman-Ford Algorithm (post #1)

(Guest post by Andrew Puleo)

As professor atri gave us at the end of last lecture, we discussed the shortest path algorithm:

$OPT(i, v) = \min\{OPT(i-1, v), \min_{(v,w) \in E} \{c_{v,w} + OPT(i-1, w)\}\}$

• $OPT(i-1,v)$ is the cost of the shortest $v-t$ path that uses  $\le i-1$ edges
• $\min_{(v,w) \in E} \{c_{v,w} + OPT(i-1, w)\}$ is the shortest path that goes through all neighbors

The shortest path algorithm will search for will ultimately give $M[v,i] = OPT(i,v)$

Shortest Path Algorithm:

1. $M[t,0] = 0$ and $v \neq t \in V$, $M[v,0] = \infty$
2. For $i=1,\dots,n-1$
1. For every $v \in V$
• $M[v,i] = \min\{M[v, i-1], \min_{(v,w) \in E} \{c_{v,w} + OPT(i-1, w)\}\}$

$M[s, n-1]$         (cost of shortest path from $s$ to $t$)

Ex:

• $M[s,1]=\min\{M[s,0],\min\{c_{s,t}+M[t,0],c_{s,u}+M[u,0]\}\}$
• $M[u,1] = \min\{\infty, 2+M[t,0]\} = 2$
• $M[t,1] = \min\{0\} = 0$
• $M[t,2] = \min\{0\} = 0$
• $M[u,2] = \min\{M[u,1], 2 + M[t,1]\} = 2$
• $M[s,2] = \min\{M[s,1], \min\{c_{s,u}+ M[u,1], c_{s,t}+ M[t,1]\}\}$

Shortest Path s-t: $M[s,2]$

-3     2

$s$ to $u$ to $latex t$

Runtime Analysis:

1. $O(n)$
2. For $i=1,\dots,n-1$ ($O(n)$)
1. For every $v \in V$($O(n)$)
• $M[v,i] = \min\{M[v, i-1], \min_{(v,w) \in E} \{c_{v,w} + OPT(i-1, w)\}\}$ ($O(n)$)

Which in total is $O(n^3)$. Thus, overall runtime is  $O(n^3)$. We can achieve runtime of $O(mn)$

Longest Path Problem:

Does the longest path have $n-1$ edges? Atri told us this was a trick problem, if you can solve it you’ll get \$1 mill

Although if using a witness (a path $v_1,\dots,v_n$)  we can check if it is the longest path or not.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 36, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9243825674057007, "perplexity": 2504.2351156143195}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2017-43/segments/1508187822747.22/warc/CC-MAIN-20171018051631-20171018071631-00513.warc.gz"}