Shortest-Path

Shortest-Path

Unter einem kürzesten Pfad versteht man in der Graphentheorie einen Pfad zwischen zwei Knoten u und v, welcher minimale Länge hat. Haben die Kanten im Graphen alle das gleiche Kantengewicht, so ist der kürzeste Pfad äquivalent zu dem Pfad mit den wenigsten Knoten. Sollten die Kanten jedoch unterschiedliche Kantengewichte haben, so ist ein kürzester Pfad nicht notwendigerweise der Pfad der durch die wenigsten Knoten verläuft.

Es sollten folgende Unterscheidungen vorgenommen werden.

  • single-pair shortest path. Der kürzeste Pfad zwischen zwei unterschiedlichen Knoten.
  • single-source shortest path (SSSP). Der kürzeste Pfad zwischen einem Startknoten und allen anderen Knoten des Graphen.
  • single-destination shortest path. Der kürzeste Pfad zwischen einem Endknoten und allen anderen Knoten des Graphen. Dies ist eine Umkehrung des SSSP und kann durch eine Umkehrung der Kantenrichtungen erreicht werden.
  • all-pairs shortest path (APSP). Der kürzeste Pfad, von jedem Knoten im Graph, zu jedem anderen Knoten.

Inhaltsverzeichnis

Anwendung

siehe: Pathfinding

Algorithmen die einen kürzesten Pfad berechnen finden häufig Anwendung in der Berechnung von Reise-Routen. So kann zum Beispiel die Entfernung zwischen zwei Städten berechnet werden. Dabei sind die Städte Knoten des Graphen, und die Straßen die Kanten.

Beispiele

Beispielgraph

Im oben gegebenen Graphen ist ein kürzester Pfad zwischen den Knoten D und C der Pfad, welcher in D startet, und über B nach C geht. Die Pfadkosten betragen hierbei 9 + 8 = 17. Will man jedoch einen Pfad von D nach E finden, so ist der direkte Weg mit Kosten von 15 nicht der kürzestmögliche Pfad, da der Weg von D über F nach E nur Kosten 14 = 8 + 6 hat.

Um kürzeste Pfade in Graphen zu berechnen kann man zum Beispiel folgende Algorithmen verwenden:

Kürzeste Wege mit Nebenbedingungen

Wenn jede Kante nicht nur Kosten hat, sondern auch Ressourcen, dann ist das Problem NP-schwer, also nicht mehr polynomiell lösbar. → siehe: SSSP mit Ressourcen

Literatur

  • Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest: Introduction to Algorithms. MIT Press, 2001, ISBN 0262531968
  • Bernhard Korte, Jens Vygen: Combinatorial Optimization. Theory and Algorithms. Springer, 2008, ISBN 978-3-540-71844-4

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Shortest Path — Unter einem kürzesten Pfad versteht man in der Graphentheorie einen Pfad zwischen zwei Knoten u und v, welcher minimale Länge hat. Haben die Kanten im Graphen alle das gleiche Kantengewicht, so ist der kürzeste Pfad äquivalent zu dem Pfad mit den …   Deutsch Wikipedia

  • Shortest path problem — A graph with 6 vertices and 7 edges In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. An example is… …   Wikipedia

  • Shortest path tree — A shortest path tree, in graph theory, is a subgraph of a given (possibly weighted) graph constructed so that the distance between a selected root node and all other nodes is minimal. It is a tree because if there are two paths between the root… …   Wikipedia

  • Shortest Path First — Алгоритмы поиска на графах A* B* Поиск в ширину Поиск в глубину Алгоритм Дейкстры Двунаправленный поиск Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Дейкстры алгоритм на графах, изобретенный Э. Дейкстрой. Находит… …   Википедия

  • shortest-path routing —    A routing algorithm in which paths to all network destinations are calculated. The shortest path is then determined by a cost assigned to each link …   Dictionary of networking

  • Shortest Path — kürzester Pfad …   Acronyms

  • Shortest Path — kürzester Pfad …   Acronyms von A bis Z

  • Open Shortest Path First — (OSPF) ist ein Verfahren aus der EDV Netztechnik. Es bezeichnet ein von der IETF entwickeltes Link State Routing Protokoll. Es ist im RFC 2328 (obsolet: RFC 1247 von 1991) festgelegt und basiert auf dem von Edsger W. Dijkstra entwickelten… …   Deutsch Wikipedia

  • Constrained Shortest Path First — (CSPF) is an extension of shortest path algorithms. The path computed using CSPF is a shortest path fulfilling a set of constraints. It simply means that it runs shortest path algorithm after pruning those links that violate a given set of… …   Wikipedia

  • Open Shortest Path First — (OSPF) is an adaptive routing protocol for Internet Protocol (IP) networks. It uses a link state routing algorithm and falls into the group of interior routing protocols, operating within a single autonomous system (AS). It is defined as OSPF… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”