Posted by: **atri** | December 11, 2009

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

*(Guest post by Chienchung Huang)*

Today’s lecture we continue the previous topic ” Shortest Path Problem” the following is the given Algorithm :

*Input:* (Directed) Graph and for every edge has a cost (can be ) and
*Output:* Shortest path from every to

As we discuss at last lecture the output shortest path will has the negative cost infinity, but the professor mentioned that we not consider negative cycle in this point of time.

**Recurrence Relation:**

- = cost of shortest path from to with at most edges
- is shortest path cost between and

There came out from last class.

Q : how to compute the shortest path between and ? (Given all values.)

**Bellman-Ford algorithm :**

Compute a matrix (ultimately )

- and for every , (no edge path from to )
- For
- For every
- .

As we know is

- I take ,
- look at all neighbor and
- as graph shown on above the and let first look at We got cost of is and .
- Look at second , and we got cost of is and
- add cost of and to get
- add cost of and to ger
- , so we pick
- Write the result to matrix , and continue the loop

**Run time analysis :**

- and ()
- For $latex = 1,\dots, n-1$ ()
- For every ()

*[There are some missing steps, see the book.–Atri]*

The running time .

**Longest Path Problem :**

*Input:* , for every , and .
*Output: * longest path between and

### Like this:

Like Loading...

*Related*

## Leave a Reply