Explore
For Enterprise
Join for Free
Log In

artes y humanidades
Negocios
Ciencias de la Computación
Ciencia de Datos
Tecnología de información
salud
Matemáticas y Lógica
Desarrollo Personal
Ciencias Físicas e Ingeniería
Ciencias sociales
Aprendizaje de un idioma
Grados
Certificados

Explorar todo lo que Coursera tiene para ofrecer

Explorar
Buscar
For Enterprise
Inicia Sesión
Únete de forma gratuita

2.5 Dijkstra Shortest Path

Loading...

C++ For C Programmers, Part A

Universidad de California en Santa Cruz

4.4 (617 calificaciones) | 93K estudiantes inscritos

This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.

Destrezas que aprenderás

Graph Theory, C++11, C++, Graph Algorithms

Revisiones

4.4 (617 calificaciones)

5 stars
402 ratings
4 stars
138 ratings
3 stars
31 ratings
2 stars
20 ratings
1 star
26 ratings

AK

Jul 04, 2017

I like Prof. Ira a lot and wish to see more courses from him! I wish I was his student at SC. Best Regards to him and the Coursera team for the great work.

PK

Jul 18, 2018

I really loved this course. It is really helpul for my programming aspect. I have managed to develop my logical abilty and this course really helped me.

De la lección

Module 2

Review of Dijkstra's shortest path algorithm. C++ Functions and Generics. C++ classes and OO. Point as an example.

2.1 C++ Generics and Functions14:13

2.2 Multiple Template Arguments8:48

2.3 Graph Theory & Algorithms9:33

2.4 Graph as a Data Structure11:10

2.5 Dijkstra Shortest Path16:42

2.6 C++ Creating Types5:22

2.7 Enum & Operator Overloading4:04

2.8 Example: typedef days18:39

2.9 Natural Way to Build Widgets6:47

2.10 C++ Point26:58

Impartido por:

Ira Pohl
Professor

Transcripción

Oh, now we're going to describe one of the most

important algorithms in computer science, the Dijkstra Shortest Path Algorithm.

Edsger Dijkstra is a Dutch computer scientist, and he's

one of the most important figures in modern computer science.

He was involved in computer language design, ideas in compiling,

ideas in the semantics, correctness of programming.

And he invented a number of very, very clever and important algorithms.

Dijkstra started his career in the Netherlands at the Mathematical Centrum.

And later became a professor at the University of Texas in the United States.

And he's also one of the very first people to

win the Turing Award, which hopefully most of you know about.

But if you don't the people who've won the Turing Award are what

the analogy is MacArthur Prizes or Nobel Prizes.

We don't have such things in computer science, per se,

and the Turing Award is considered our Nobel Prize.

So in the Dijkstra Shortest Path Algorithm that we're going to

describe, we're going to use undirected graphs with weightings(with cost).

So costs are going to all be non-negative.

And conceptually, what you should keep in mind is a road map, and

the canonical problem is finding the shortest route from one place to another.

So, if you're looking for a road trip and you're going between Chicago and Los

Angeles, and you want a shortest path, you have a very big map.

Lots of roads.

You typically might go to AAA and get some specific assistance.

Or nowadays, you can just use

your on-board trip computer.

And they indeed in, in some important sense (it has embeded )the Dijkstra algorithm.

We're going to learn how to program this critical

algorithm and indeed, it's going to be our next programming assignment.

So, the idea is we have a source and a destination.

Chicago to Los Angeles.

And between the source and destination, we

want to find a shortest path. The

critical steps in the Dijkstra algorithm are to maintain what

I call two sets. One is a set of closed nodes.

The closed nodes

are nodes that

have, have known

shortest distances.

Now if we're starting from Chicago, what do we know?

Right off the cuff, we know the shortest distance from Chicago to Chicago.

That's zero.

That's like trivial case. So, the algorithm would start with the

source node being put in the closed set, and that source node would have value 0.

And then, in the open

set, we would look for immediate

successors of s. And place their distance in the open set.

So the open set is what's reachable. And

at any time in the open set,

we have what's reachable.

And we have a calculation based on the edge cost from things in

the closed set. And what we do, our major iterative step

is we pick the open note in that list, who's cost is least.

Pick the open node who has least cause.

Whoops, least cost, not list cost, least cost.

Confusing list and least. Okay.

If in this iterative step, we pick a node that is the termination node.

If we've, are moving along from Chicago, and we've reached Los Angeles.

And Los Angeles gets thrown in the closed set, we can stop.

The algorithm guarantees that when the destination node

is placed in the closed set, calculation is provably

a shortest distance. If the

destination node is not the node picked as the next least node from the

open set, we compute all the direct successors from

that node. So if that node,

so we, n has least cost.

We look at the edges out of n.

And they have a cost. It might be cost of n to j, where

(n,j) are the determiners of the edge.

And n will have a value, which is its value of

the, the cost from s, from the source. So n has some cost,

some current

cost, back to s.

And that cost, whatever that is, s to n

plus cost ( n , j) is what

it takes to reach j. Now either j is already in the open set.

we have like, three cases. J is in the closed set.

If j was already in the closed set, we don't need to bother with it, because

we already know by the nature of Dijkstra's

algorithms that we have a shortest path to j.

If j is not in the open set, or the closed set, then we put it in the open set.

We now have a new path, a way to get to j. So we're somewhere, past Chicago.

Maybe we're approaching Kansas City and we haven't yet reached Kansas City

in any kind of path that we've calculated. And we see we can get to Kansas City.

That would be placed in the open set with whatever

it's value is, traced back to Chicago.

And the last case is, we already had an alternative route.

We had a pre-computed route.

So j, or Kansas City, in this case, was already in the open set.

But this new route improves on the old route

because we're trying to search for least costly paths.

In that case we update the paths.

So we have three conditions, open set, a possibility for updating, or

it's already in the closed set. And then if the node d is picked, we stop.

There's no further need to look for successors.

Or if there's no more successors, we can't get to d.

So if we try to go from Chicago to Honolulu, we would find all sorts of

paths to places like Seattle and El Paso, and God

knows what else, Los Angeles, but we would have no road

route to Honolulu. So we would exhaust, if we had tried

to put into our travel

computer, find me a road from Chicago to Honolulu, it would stop.

And otherwise some shortest path tree is maintained in the calculation.

And that lets us, when it's done, having stopped at d, not only have

the value of the shortest route but be able to trace back the shortest route.

So I'm going to simulate Dijkstra by hand.

And I'm going to simulate it on this next map.

And I'm going to draw things in red and I'm going to start with S.

And I'm going to want to get us to T.

In this case, I'm doing it in a directed graph.

So this was just the case that I had manufactured and I'll show it to you in

the directed case, but it, it shouldn't be any different in the undirected case.

So initially, the open set s has value 0, and

then s can reach a.

So this is the closed set, and its value is 4.

S can reach b,

and its value is 3. S can reach

d, and its value is 7. And that's it.

The out degree edges of s are 3.

So now we look at the open set. We pick s equals b,

so b comes into the closed set with value 3.

So in some sense, Dijkstra's algorithm has picked out this.

And now b becomes the node we expand from, and so we search b.

Now b can go back to s, but that's not a value, since s is in a closed set.

And b can go to d.

So we have to check if b went to d, it would be 3 plus 4.

But we

already of d at 7, so there's no reason to update it.

And that's the only two ways we can go. So there isn't anything new in

the open set. So we would come back, and we would get as

our least value, a, whose value is 4. And

so now, our Dijkstra's shortest path tree would be

at this point in the second iteration also s going to a with 4.

Now a has some new things we can go to. So from a we can go to

c. The value was 4 plus 1, so now it's 5.

And that's the only thing a can go to. But 5 is indeed

the best value, so we put in c in the closed set.

The c's value equal 5.

And c can reach e with

value 6. And c can

reach d, and that would

be value 8. 8 doesn't

improve on 7, so we don't update that. But we can

go c to e, and that's value 6. So now we cross out this.

We get e.

We get it equal 6. We go back and we find we can go to e.

Oops, no e already went to (6 -sic).

Excuse me, we go back and e is now in the open set.

e has to be expanded. So we get, we can look at e to d.

Now e can't go to d directly, that's the wrong direction.

But e can go to g and g is value 8.

And e can go to t, so it can go to g for value 8.

It can go to t,

and that's value 10.

Now just because we can reach t, which is

our destination, the terminus, doesn't mean we go there.

because this is still in the open set.

The only time we're guaranteed a best or least costly path

is when something's been stored in the, in the closed set.

And there's still values less than 10. So they have to be explored.

The next value that needs to be explored is s going to d at 7.

So s going to d at 7 makes d equal 7 in the closed set.

And then we have d can go to f.

So 7 plus 5 is 12. d from here can go to

t. So that's 7 plus 3, which is 10.

But that hasn't improved the value, so we don't update anything.

And d can go to e, but e is in the closed set, so we don't do anything with that

either. So here we go back, we look.

We've got an e

going to g (value) 8.

And from g, we can go back to e. e is already in the closed set.

We can from g to t.

But 8 plus 3 is 11. We don't improve on 10.

So we leave it alone.

We're done with the updates. We come back, select the node.

And now we find e to t, which is value 10. And e to t,

so t equals 10. We can terminate.

And if we keep our

back lengths in this map, we can even find the shortest path.

Now notice it wasn't unique.

We could have found the shortest paths, which would have been s to d and d to t.

That would have also been 10.

So this doesn't guarantee any kind of uniqueness, but

it does guarantee that we get a least costly path.

You should practice with other graphs.

And the assignment I'm giving out now is that you will try to do a

Dijkstra Shortest Path Algorithm, which will mean

that you need to decide on a representation.

my recommendation is the list representation's a little more flexible.

But it's perfectly okay if you do the matrix

representation, or even do both, depending on how ambitious you are.

And that'll be an assignment that I'll be expecting for the next turn in time.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play

Coursera
Acerca de
Liderazgo
Empleo
Catálogo
Certificados
Certificados MasterTrack™
Grados
For Enterprise
For Government

Comunidad
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Blog de Tecnología

Más
Términos
Privacidad
Ayuda
Accesibilidad
Prensa
Contacto
Directorio
Afiliados