The Internet belongs to everyone. Let’s keep it that way.

Protect Net Neutrality
Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Dijkstra Algorithmus

No description
by

Anna Nguyen

on 19 January 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Dijkstra Algorithmus

Verwendung
Quellen
Edsger W. Dijkstra
Zusammenfassung
Gliederung
http://de.wikipedia.org/wiki/Edsger_W._Dijkstra
http://www.gitta.info/Accessibiliti/en/html/Dijkstra_learningObject3.html
https://bisor.wiwi.uni-kl.de/orwiki/Dijkstra_Algorithmus
http://fuzzy.cs.uni-magdeburg.de/studium/graph/txt/duvigneau.pdf
http://www.unibw.de/inf4/professuren/geoinformatik/lehre/skripten/skripte/skripten_ht_11/gi2-kap7-wege.pdf
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
Edsger Wybe Dijkstra
* 11. Mai 1930 in Rotterdam; † 6. August 2002 in Nuenen
niederländischer Informatiker
Pionier der strukturierten Programmierung
1972: Turing Award
Gegeben:
Graph mit kostenattributierten Kanten (z.B. Strecke, Zeit)
Aufgabe:
Berechnung des kürzesten Weges vom Startknoten s zu Zielknoten z
Idee:
alle Wege berechnen und kürzesten auswählen
Feststellung:
kürzester Weg von s zu z über y -> Teilstücke immer kürzester Weg zwischen beiden Knoten
Dijkstra Algorithmus:
Berechnung der kürzesten Wege von beliebigen Startpunkt zu allen anderen Knoten des Graphen
Edsger W. Dijkstra
Grundlegendes Konzept des Algorithmus
Beispiel
Verwendung
Kritik
Zusammenfassung
Quellen
Berechnung des kürzesten Weges in einem Graphen
gesucht: optimaler Weg
Idee:
immer denjenigen Kanten folgen, die kürzesten Streckenabschnitt vom Startknoten
erst dann verfolgt, wenn alle Streckenabschnitte beachtet wurden
gewährleistet kürzeste Pfade
Dijkstra Algorithmus
Beispiel:
Kritik
Grundlegendes Konzept des Algorithmus
Dijkstra 2002
Routing in Computernetzwerken
Routenplanung
beispielsweise:
Anwendung in realen Netzen
Größe des Netzwerkes (Effizienz)
Straßenverkehrsordnung (Abbiege- und Wendeverbote)
siehe Tafel
Full transcript