Shortest path problem: Unterschied zwischen den Versionen

GISWiki - Das freie Portal für Geoinformatik (GIS)
Wechseln zu: Navigation, Suche
(Definitionen)
K (Wege, Pfade, Zyklen und Kreise in Graphen wurde nach Shortest path problem verschoben)
 
(3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
{{Deutsch}}
+
<h1>{{Deutsch}}</h1>
 +
 
 
'''Wege''', '''Pfade''', '''Zyklen''' und '''Kreise''' sind Begriffe der [[:de:Graphentheorie|Graphentheorie]] und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem [[:de:Graph (Graphentheorie)|Graphen]]. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem Übersichtsartikel zusammen dargestellt.  
 
'''Wege''', '''Pfade''', '''Zyklen''' und '''Kreise''' sind Begriffe der [[:de:Graphentheorie|Graphentheorie]] und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem [[:de:Graph (Graphentheorie)|Graphen]]. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem Übersichtsartikel zusammen dargestellt.  
  
Zeile 66: Zeile 67:
 
* Wikipedia: [[:de:Wege, Pfade, Zyklen und Kreise in Graphen|Wege, Pfade, Zyklen und Kreise in Graphen]]
 
* Wikipedia: [[:de:Wege, Pfade, Zyklen und Kreise in Graphen|Wege, Pfade, Zyklen und Kreise in Graphen]]
  
<h1>English</h1>
+
<h1>{{English}}</h1>
  
 
In [[:en:graph theory|graph theory]], the '''single-source shortest path problem''' is the problem of finding a [[:en:path (graph theory)|path]] between two vertices such that the sum of the weights of its constituent edges is minimized. More formally, given a weighted graph (that is, a set ''V'' of vertices, a set ''E'' of edges, and a [[:en:real number|real]]-valued weight function ''f''&nbsp;: ''E''&nbsp;&rarr;&nbsp;'''R'''), and given further one element ''n'' of <i>N</i>, find a path ''P'' from ''n'' to each ''n' '' of <i>N</i> so that
 
In [[:en:graph theory|graph theory]], the '''single-source shortest path problem''' is the problem of finding a [[:en:path (graph theory)|path]] between two vertices such that the sum of the weights of its constituent edges is minimized. More formally, given a weighted graph (that is, a set ''V'' of vertices, a set ''E'' of edges, and a [[:en:real number|real]]-valued weight function ''f''&nbsp;: ''E''&nbsp;&rarr;&nbsp;'''R'''), and given further one element ''n'' of <i>N</i>, find a path ''P'' from ''n'' to each ''n' '' of <i>N</i> so that

Aktuelle Version vom 5. März 2006, 13:57 Uhr

Deutsch

Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem Übersichtsartikel zusammen dargestellt.

Definitionen

Gerichtete und ungerichtete Wege

Sei G=(V, E) ein (gerichteter) (Multi-)Graph und W=(v1,...,vn) eine Folge von Knoten aus V, mit der Eigenschaft, dass für alle i aus {1,...,n-1} gilt:

  • Die Menge {vi,vi+1} ist Element von E, falls G ein ungerichteter Graph ohne Mehrfachkanten ist,
  • Das Paar (vi,vi+1) ist Element von E, falls G ein gerichteter Graph ohne Mehrfachkanten ist,
  • E({vi,vi+1})>0, falls G ein ungerichteter Graph mit Mehrfachkanten ist,
  • E((vi,vi+1))>0, falls G ein gerichteter Graph mit Mehrfachkanten ist,

das heißt vi und vi+1 sind durch eine Kante verbunden. Dann bezeichnet man W als ungerichteten Weg in G, falls G ungerichtet ist, und als gerichteten Weg in G, falls G gerichtet ist. Eine andere Bezeichnung für Weg ist Kantenfolge. Den Knoten v1 nennt man Startknoten von W und den Knoten vn Endknoten von W.

Pfade, Zyklen und Kreise

Ferner bezeichnet man W statt als Weg, spezieller als

  • Pfad, falls alle Knoten in der Folge W voneinander verschieden sind, das heißt falls für alle i und j aus {1,...,n} gilt, dass vi?vj, falls i?j.
  • Zyklus, falls Start- und Endknoten von W identisch sind, das heißt falls v1=vn.
  • Kreis, falls nur Start- und Endknoten von W identisch sind, das heißt falls v1=vn und vi,...,vi-1 einen Pfad bilden, also für alle i und j aus {1,...,n-1} gilt, dass vi?vj, falls i?j.

Bemerkung: Jeder Kreis, Zyklus und Pfad in einem Graphen G ist also auch ein Weg und jeder Kreis ist auch ein Zyklus in G. Wege, Pfade, Zyklen und Kreise definiert man alternativ auch über Kantenzüge oder de:Teilgraphen. Gibt es einen Weg von Knoten u zu Knoten v in G, so heißt v von u aus erreichbar (Erreichbarkeitsproblem in Graphen).

In ungerichteten Wegen und Pfaden bezeichnet man den Startknoten meist ebenfalls als Endknoten. In Zyklen und Kreisen verwendet man die Bezeichnungen Startknoten und Endknoten meist nicht.

Graphen mit Zyklen heißen zyklisch. Graphen ohne Zyklen heißen azyklisch.

Ein Zyklus oder Kreis heißt trivial, wenn er weniger als 3 Knoten enthält. Triviale Kreise oder Zyklen werden meist nicht betrachtet.

Ein Kreis, der genau 3 Knoten enthält nennt man oft Dreieck. Ein Graph ohne Dreieck nennt man dann dreiecksfrei.

A-B-Weg, v-w-Weg, a-B-Fächer

Sind A und B Teilmengen von V, so bezeichnet man einen Weg als A-B-Weg, falls der Startknoten in A und der Endknoten in B liegt. Statt von einem {v}-{w}-Weg spricht man auch von einem v-w-Weg.

Eine Menge von a-B-Wegen nennt man einen a-B-Fächer, wenn die Wege paarweise nur den Knoten a gemeinsam haben.

kreuzungsfrei, knotendisjunkt, kantendisjunkt

Zwei Wege W1=(v1,1,...,v1,k) und W2=(v2,1,...,v2,l) heißen kreuzungsfrei, knotendisjunkt oder einfach nur disjunkt, falls es kein Paar (i,j) mit i aus {2,...,k-2} und j aus {2,...,l-2} gibt, so dass v1,i=v2,j, das heißt, wenn sie keine inneren Knoten gemeinsam haben. Eine Menge von Wegen nennt man kreuzungsfrei, knotendisjunkt oder disjunkt, wenn die Wege paarweise disjunkt sind. Zwei Wege W1=(v1,1,...,v1,k) und W2=(v2,1,...,v2,l) heißen kantendisjunkt, falls es kein Paar (i,j) mit i aus {1,...k-1} und j aus {1,...,l-1} gibt, so dass v1,i=v2,j und v1,i+1=v2,j+1. Eine Menge von Wegen nennt man kantendisjunkt, wenn die Wege paarweise kantendisjunkt sind.

Länge eines Weges (Zyklus, Kreises), Abstand

In Graphen ohne Gewichte auf den Kanten bezeichnet man mit n-1 die Länge eines Weges (oder Pfades) und mit n die Länge eines Zyklus (oder Kreises) (v1,...,vn). Anschaulich zählt man also die Anzahl zugehöriger Kanten.

In kantengewichteten Graphen bezeichnet man als Länge eines Weges die Summe der Kantengewichte aller zugehörigen Kanten. Als einen kürzesten Weg von einem Knoten s zu einem Knoten t in einem Graphen bezeichnet man einen Weg von s nach t, dessen Länge minimal ist. Die Länge eines kürzesten Weges nennt man dann Abstand oder Distanz von s nach t. Falls kein Weg zwischen zwei Knoten existiert, so setzt man den Abstand auf unendlich. Man beachte, dass in gerichteten Graphen der Abstand von der Richtung des Weges abhängt. Insbesondere kann es sein, dass nur in eine Richtung ein gerichteter Weg existiert.

Durchmesser und Taillenweite

Den größten Abstand zwischen zwei Knoten in einem Graphen G nennt man Durchmesser von G. Als Taillenweite eines Graphen bezeichnet man die Länge eines kürzesten nicht trivialen Kreises. Falls der Graph keinen Kreis besitzt, so setzt man die Taillenweite auf unendlich.

Distanzgraph

Der Distanzgraph zu einem Graphen G=(V,E) bezeichnet den vollständigen (das heißt je zwei Knoten sind durch eine Kante verbunden, ggf. in gerichteten Graphen in beide Richtungen, wobei es aber keine Schleifen gibt) kantengewichteten Graphen auf der Knotenmenge V, der jeder Kante als Kantengewicht den Abstand zwischen den beiden Knoten in G zuordnet.

Wichtige Algorithmen

Der Algorithmus von Dijkstra findet einen kürzesten Pfad zwischen zwei beliebigen Knoten in einem (kantengewichteten) Graphen. Mit seiner Hilfe lässt sich auch der Distanzgraph bestimmen, indem man ihm ausgehend von jedem Knoten den Abstand zu jedem anderen bestimmt. Für jeden Knoten ist dabei nur ein Aufruf des Algorithmus von Dijkstra nötig, da dieser auch den Abstand von einem Knoten zu allen anderen Knoten bestimmen kann.

Der Distanzgraph ist für das Problem des Handlungsreisenden interessant, da dieser metrisch ist, weshalb verschiedene Approximationsalgorithmen dieses Problem wenigstens annähernd lösen können und die Lösung auf dem Distanzgraphen in der Praxis ausreicht.

Siehe auch

English

In graph theory, the single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. More formally, given a weighted graph (that is, a set V of vertices, a set E of edges, and a real-valued weight function f : E → R), and given further one element n of N, find a path P from n to each n' of N so that

<math>\sum_{p\in P} f(p)</math>

is minimal among all paths connecting n to n' . The all-pairs shortest path problem is a similar problem, in which we have to find such paths for every two vertices n to n' .

A solution to the shortest path problem is sometimes called a pathing algorithm. The most important algorithms for solving this problem are:

  • Dijkstra's algorithm — solves single source problem if all edge weights are greater than or equal to zero. Without worsening the run time, this algorithm can in fact compute the shortest paths from a given start point s to all other nodes.
  • Bellman-Ford algorithm — solves single source problem if edge weights may be negative.
  • A* algorithm (or A* pathing algorithm) — a heuristic for single source shortest paths.
  • Floyd-Warshall algorithm — solves all pairs shortest paths.
  • Johnson's algorithm — solves all pairs shortest paths, may be faster than Floyd-Warshall on sparse graphs.

A related problem is the traveling salesman problem, which is the problem of finding the shortest path that goes through every node exactly once, and returns to the start. That problem is NP-Complete, so an efficient solution is not likely to exist.

In a networking or telecommunications mindset, this shortest path problem is sometimes called the min-delay path problem and usually tied with a widest path problem. e.g.: Shortest (min-delay) widest path or Widest shortest (min-delay) path.

Literatur / Literature