Location: Academic Organisations » OpenCourseWare Consortium » MIT OpenCourseWare » MIT 6.046J / 18.410J Introduction to Algorithms - Fall 2005

event thumbnail image

MIT 6.046J / 18.410J Introduction to Algorithms - Fall 2005

Lecture 18: Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints

author:Erik Demaine, Center for Future Civic Media
published: Feb. 10, 2009, recorded: November 2005, views: 2999

Turn off the lights

You might be experiencing some problems with Your Video player.

Slides

Slides
0:00	Introduction to Algorithms - Lecture 18
2:06	Negative-weight cycles
4:29	Bellman-Ford algorithm
10:15	Example of Bellman-Ford (1)
11:58	Example of Bellman-Ford (2)
12:51	Example of Bellman-Ford (3)
13:13	Example of Bellman-Ford (4)
13:17	Example of Bellman-Ford (5)
13:19	Example of Bellman-Ford (6)
13:23	Example of Bellman-Ford (7)
13:47	Example of Bellman-Ford (8)
14:02	Example of Bellman-Ford (9)
14:07	Example of Bellman-Ford (10)
14:38	Example of Bellman-Ford (11)
14:43	Example of Bellman-Ford (12)
14:55	Example of Bellman-Ford (13)
15:08	Example of Bellman-Ford (14)
15:12	Example of Bellman-Ford (15)
15:28	Example of Bellman-Ford (16)
15:32	Example of Bellman-Ford (17)
15:37	Example of Bellman-Ford (18)
15:43	Example of Bellman-Ford (19)
15:49	Example of Bellman-Ford (20)
16:16	Example of Bellman-Ford (21)
18:39	Correctness (1)
19:42	Correctness (2)
24:38	Correctness (3)
33:12	Detection of negative-weight cycles
36:20	Linear programming
42:38	Linear-programming algorithms (1)
45:56	Linear-programming algorithms (2)
47:28	Solving a system of difference constraints (1)
50:10	Solving a system of difference constraints (2)
50:53	Solving a system of difference constraints (3)
53:42	Unsatisfiable constraints (1)
54:54	Unsatisfiable constraints (2)
57:11	Unsatisfiable constraints (3)
59:05	Satisfying the constraints (1)
60:37	Satisfying the constraints (2)
61:56	Satisfying the constraints (3)
64:29	Satisfying the constraints (3)
68:16	Bellman-Ford and linear programming
72:29	Application to VLSI layout compaction
74:54	VLSI layout compaction

Related content

Visitors who watched this lecture also watched...

Lecture 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search
3998 views - Erik Demaine, 2005

Lecture 19: Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson
971 views - Erik Demaine, 2005

Lecture 16: Greedy Algorithms, Minimum Spanning Trees
1696 views - Charles E. Leiserson, 2005

Lecture 15: Dynamic Programming, Longest Common Subsequence
2044 views - Charles E. Leiserson, 2005

Lecture 31: Simplex method in linear programming
1423 views - Gilbert Strang, 2001

Lecture 22: Advanced Topics
411 views - Charles E. Leiserson, 2005

Lecture 2: Asymptotic Notation, Recurrences, Substitution, Master Method
3671 views - Erik Demaine, 2005

Lecture 1: Administrivia, Introduction, Analysis of Algorithms, Insertion Sort, Mergesort
4050 views - Charles E. Leiserson, 2005

Lecture 30: Network flows and combinatorics: max flow = min cut
599 views - Gilbert Strang, 2001

Lecture 10: Red-black Trees, Rotations, Insertions, Deletions
3214 views - Erik Demaine, 2005

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Lecture popularity: You need to login to cast your vote.

Description

"Good morning, everyone. Glad you are all here bright and early. I'm counting the days till the TA's outnumber the students. They'll show up. We return to a familiar story. This is part two, the Empire Strikes Back. So last time, our adversary, the graph, came to us with a problem. We have a source, and we had a directed graph, and we had weights on the edges, and they were all nonnegative. And there was happiness. And we triumphed over the Empire by designing Dijkstra's algorithm, and very efficiently finding single source shortest paths, shortest path weight from s to every other vertex...

See Also:

Download slides icon Download slides: mit6046jf05_demaine_lec18_01.pdf (286.5 KB)

Launch Windows Media Player Launch in a standalone WM Player

WMedia Player Switch to Windows Media Player

Download Flash video Download mit6046jf05_demaine_lec18_01.flv (Flash video 213.3 MB)

Download mp4 video Download mit6046jf05_demaine_lec18_01.m4v (mp4 video 159.8 MB)

Download Real media video Download mit6046jf05_demaine_lec18_01.rm (Real media video 123.6 MB)

Download Windows Media video Download mit6046jf05_demaine_lec18_01.wmv (Windows Media video 681.1 MB)

Download audio transcript Download mit6046jf05_demaine_lec18_01.mp3 (Audio transcript 17.8 MB)

Help icon Streaming Video Help

WebLink icon Windows Media Player Firefox Plugin - Download

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment

1 mohamad, December 15, 2009 at 2:10 a.m.:

thanks.. your lessons really do help.. just found this site today... i'll probe into it to see find other useful stuff.. thanks a lot.

Comment

2 tomy dragon, December 17, 2009 at 9:32 a.m.:

Thanks alot! Very usefull

Write your own review or comment:

Comment
Name
Email address
URL

make sure you have javascript enabled or clear this field: