# 16. Dijkstra

474 26 121533

Uploaded on
01/14/2013

MIT 6.006 Introduction to Algorithms, Fall 2011

View the complete course: http://ocw.mit.edu/6-006F11

Instructor: Srini Devadas

License: Creative Commons BY-NC-SA

More information at http://ocw.mit.edu/terms

More courses at http://ocw.mit.edu

Comments (2):

Submit Your Video

By anonymous 2017-09-20

You should use

`priority queue`

where the`vertex`

with the shortest distance from the starting`vertex`

will get the highest priority. Initially, all`vertices`

will have the shortest distance of infinity and the starting`vertex`

will have the shortest distance 0.Start by inserting of all

`vertices`

(with its`edges`

) from the graph inside the`PQ`

. Remove`vertex`

from the`PQ`

and explore all its`edges`

. Compare the shortest distances with all adjacent`vertices`

and if any distance is less than the shortest distance on the current`vertex`

, update adjacent`vertex`

shortest distance inside the`PQ`

. Continue while`PQ`

is not empty.`Vertices`

which got no`edges`

will finish with the shortest distance of infinity because it is not possible 'get to them' from the starting`vertex`

. However, they will be still removed from the`PQ`

.PseudocodeMIT OpenCourseWare Links:Path problems overview

Dijkstra

Original Thread