Die selbst¨ andige und eigenh¨ andige Anfertigung dieser Arbeit versichere ich an Eides Statt.

Berlin, den 13. Mai 2002

Fabian Zenzinger

Vorwort

Die Anzahl registrierter Autos hat in vielen Industrienationen inzwischen einen kritischen Stand erreicht. Da sie allem Anschein nach weiter wachsen wird, die Infrastruktur jedoch nicht mehr beliebig ausbaubar ist, droht aufgrund der daraus folgenden Verkehrsdichte schon bald ein rapides Zunehmen an Staus.

Um dies zu vermeiden, versuchen einige Automobilhersteller seit einiger Zeit, sogenannte Navigationssysteme f¨ ur ihre Wagen zu entwickeln, mit denen die Verkehrsteilnehmer m¨ oglichst schnell durch den Verkehr geleitet werden sollen. Der n¨ achstliegende Ansatz bestand zuerst darin, f¨ ur jeden Teilnehmer den schnellsten Weg von seinem Start- zu seinem Zielort zu berechnen. Dies l¨ asst sich mathematisch durch das sogenannte K¨ urzeste-Wege-Problem mit nicht-negativen Kantengewichten modellieren, welches in polynomialer Zeit l¨ osbar ist. Wie sich jedoch schon bald herausstellte, sind in der Praxis weitere Komponenten zu ber¨ ucksichtigen, die die Berechnung eines f¨ ur jeden Fahrer akzeptablen Weges erschweren. So w¨ are es zum Beispiel denkbar, bei der Berechnung des schnellsten Weges zu fordern, dass der Fahrer keinen allzu grossen Umweg zu nehmen hat. Ein solcher ressourcenbeschr¨ ankter k¨ urzester Weg l¨ asst sich leider nicht in polynomialer Zeit ermitteln, da es sich dabei um ein sogenanntes schwach NP-vollst ¨ andiges Problem handelt.

Ziel der vorliegenden Arbeit ist es, Algorithmen zu entwickeln, die dieses Problem m¨ oglichst schnell l¨ osen, und zu untersuchen, welche am besten f¨ ur den Einsatz in einem solchen Route-Guidance-System geeignet sind. Zu diesem Zweck wird der f¨ ur das klassische K¨ urzeste-Wege-Problem h¨ aufig benutzte Di jkstra-Algorithmus an die neue Problemstellung angepasst und in mehreren Varianten mit unterschiedlichen Beschleunigungsmethoden implementiert. Diese werden dann auf verschiedenen Beispielinstanzen sowohl untereinander als auch im Vergleich mit f¨ ur andere Projekte verwendeten L¨ osungsverfahren getestet. Anhand der daraus folgenden Ergebnisse werden dann noch einmal zusammenfassend die Vorz¨ uge und Nachteile der jeweiligen Ans¨ atze diskutiert, bevor wir abschließend vorschlagen, welches Verfahren f¨ ur den Gebrauch als Unterproblem in einem an der TU Berlin entwickeltes Navigationssystem vorzuziehen ist.

Um dem Leser die M¨ oglichkeit zu geben, die durch die zus¨ atzliche Ressourcenbeschr¨ ankung vorgenommenen ¨ Anderungen am Ausgangsalgorithmus nachzuvoll-

i

ii

ziehen, werden in einer Einf¨ uhrung (Kapitel 2) noch einmal das K¨ urzeste-Wege-Problem sowie der Dijkstra-Algorithmus skizziert. F¨ ur ein besseres Verst¨ andnis setzt die Arbeit lediglich Grundkenntnisse in Graphentheorie und Optimierung voraus.

Ein besonderes Dankesch¨ on geht an Dr. Ekkehard K¨ ohler f¨ ur die Betreuung w¨ ahrend der Erstellung dieser Arbeit, an meine Korrekturleser f¨ ur das Aufsp¨ uren von Fehlern und an die anderen Diplomanden der Arbeitsgruppe f¨ ur die hilfreichen Ratschl¨ age w¨ ahrend der Programmierung der Algorithmen.

Inhaltsverzeichnis

Vorwort   

1  Einleitung  1

1.1  Anwendungsgebiete  1

1.2  Das CMCF Route-Guidance-Projekt an der TU Berlin  2

1.3  Das CNOP-Paket  3

1.4  Anforderungen an die Probleml osungen  4

2  Beschleunigungsmethoden f ur das K urzeste-Wege-Problem mit nicht-  

negativen  Kantengewichten  6

2.1  Problemstellung  6

2.2  Der Dijkstra-Algorithmus  7

2.2.1  Formulierung  7

2.2.2  Korrektheit und Laufzeit  8

2.3  Beschleunigungsmethoden f ur den Dijkstra-Ansatz  9

2.3.1  Der zielgerichtete Ansatz  10

2.3.2  Der bidirektionale Ansatz  12

2.3.3  Verbindung des zielgerichteten und des bidirektionalen  

Ansatzes   14

3  Ressourcenbeschr ankte Wege  17

3.1  Problemstellung  17

3.1.1  Das ressourcenbeschr ankte K urzeste-Wege-Problem  18

3.1.2  Pareto-optimale ressourcenbeschr ankte Wege  19

iii

iv

3.1.3 Das doppelt beschr¨ ankte Problem . . . . . . . . . . . . . 20

3.1.4 Beziehung zwischen den drei betrachteten Problemen . . . 21

3.2 Grundlegende Eigenschaften des ressourcenbeschr¨ ankten K¨ urzeste-Wege-Problems . . . . . . . . . . . . . . . . . . . . . . 22

3.2.1 Komplexit¨ at . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.2.2 Bisherige Ans¨ atze . . . . . . . . . . . . . . . . . . . . . 23

3.3 Der erweiterte Dijkstra-Algorithmus . . . . . . . . . . . . . . . . 24

3.3.1 Die Grundversion . . . . . . . . . . . . . . . . . . . . . . 25

3.3.2 Die zielgerichtete Version . . . . . . . . . . . . . . . . . 26

3.3.3 Die bidirektionale Version . . . . . . . . . . . . . . . . . 29

3.3.4 Die bidirektional zielgerichtete Version . . . . . . . . . . 31

3.3.5 Versionen mit zus¨ atzlichem Abbbruchkriterium . . . . . . 33

3.4 Weitere L¨ osungsmethoden . . . . . . . . . . . . . . . . . . . . . 34

3.4.1 Der Labeling-Ansatz im CMCF-Projekt . . . . . . . . . . 34

3.4.2 Die 2-Phasen-Methode im CNOP-Paket . . . . . . . . . . 36 3.5 ¨ Uberblick ¨ uber die vorgestellten Algorithmen . . . . . . . . . . . 42

4 Implementation und Geschwindigkeitsvergleiche 43

4.1 Angaben zur Implementation . . . . . . . . . . . . . . . . . . . . 43

4.1.1 Verwendete Datenstrukturen . . . . . . . . . . . . . . . . 43

4.1.2 Korrektur von Rechnerungenauigkeiten . . . . . . . . . . 44

4.1.3 Einlesen des Verkehrsnetzwerkes . . . . . . . . . . . . . 46

4.1.4 Besonderheiten beim Aufruf des CMCF-Programms . . . 47

4.2 Vergleiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.2.1 Tests auf LEDA-Graphen . . . . . . . . . . . . . . . . . . 48

4.2.2 Tests auf Raw-Graphen . . . . . . . . . . . . . . . . . . . 55

5 Zusammenfassung 63

5.1 Interpretation der Ergebnisse . . . . . . . . . . . . . . . . . . . . 63

5.2 Empfehlung f¨ ur das Route-Guidance-Projekt an der TU Berlin . . 64

Liste der Algorithmen 65

Literaturverzeichnis 68

Kapitel 1

Einleitung

K¨ urzeste-Wege-Probleme entstehen immer dann, wenn G¨ uter oder Daten in Netzwerken so schnell oder so g¨ unstig wie nur m¨ oglich von einem Punkt zu einem anderen gelangen sollen. Meistens reicht es aus, die Wege nur bez¨ uglich einer Komponente zu betrachten, sei diese nun Zeitaufwand, Wegl¨ ange oder auch entstandene Kosten.

In der Praxis gibt es jedoch auch h¨ aufig komplexere Fragenstellungen; hin und wieder werden Wege gesucht, die hinsichtlich mehr als nur einer Komponente effizient sein sollen. Dabei passiert es h¨ aufig, dass die daraus resultierenden Ziele im Widerspruch zueinander stehen und deswegen nicht gleichzeitig optimiert werden k¨ onnen. Dies ist insbesondere bei betriebswirtschaftlichen Erw¨ agungen der Fall. Ein Lastwagenfahrer hat zum Beispiel seine Waren so schnell wie m¨ oglich zum Zielort zu bef¨ ordern, muss bei seiner Routenwahl aber auch darauf achten, dass er nicht zuviel Maut und Benzin zu zahlen hat. In solchen F¨ allen muss entschieden werden, welcher Parameter am wichtigsten ist. Es wird dann eine Komponente optimiert, w¨ ahrend alle anderen eine gewisse Schranke nicht ¨ uberschreiten d¨ urfen.

In dieser Arbeit wird der Fall betrachtet, in dem es zus¨ atzlich zu den zu minimierenden Kosten genau eine andere Ressource gibt, die unter einem vorgegebenen Wert bleiben muss. Dieses Kapitel zeigt einige Verwendungsm¨ oglichkeiten aus der Praxis f¨ ur dieses Problem auf, wobei wir genaueres Augenmerk auf die Projektumgebungen legen, in denen die hier erstellten Algorithmen getestet werden. Außerdem wird darauf eingegangen, welche besonderen Eigenschaften die L¨ osungen des Problems haben m¨ ussen.

1.1 Anwendungsgebiete

Die Suche nach einem g¨ unstigen Weg bez¨ uglich zweier Komponenten tritt in einer Großzahl von Praxisbeispielen auf. So ergibt sich in Kommunikationsnetzwerken

1

2

der Fall, dass man sowohl g¨ unstig als auch relativ sicher Daten von einem Punkt zu einem anderen senden will. Dieses sogenannte Quality of Service-Problem wird unter anderen von Orda [15] betrachtet. Gerade durch die in den letzten Jahren vorangetriebene Entwicklung des Internets hat diese Fragestellung an Wichtigkeit gewonnen. Insbesondere in IP-basierten Netzwerken gibt es eine Vielzahl an Parametern, die als Nebenbedingung in Frage kommen, so dass IT -Firmen daran interessiert sind, eine Software zu entwickeln, welche f¨ ur jede Systemumgebung die relevanten Parameter ermittelt und diese dann als Kostenarten f¨ ur ein K¨ urzeste-Wege-Problem mit Nebenbedingung ¨ ubernimmt.

Doch auch in traditionellen Industriebranchen gibt es interessante Einsatzm¨ oglichkeiten. Elimam und Kohler [6] untersuchen zun¨ achst die optimale Abfolge von Abwasserfl¨ ussen einer gleichzeitig von einer industriellen und einer sanit¨ aren Organisation benutzten Einrichtung in Kuwait und gehen danach auf das Problem ein, Geb¨ aude m¨ oglichst g¨ unstig zu bauen unter der Voraussetzung, dass sie den staatlichen Sicherheitsvorschriften der USA entsprechen. Sie stellen dabei fest, dass sich beide Fragestellungen als ressourcenbeschr¨ ankte K¨ urzeste-Wege-Probleme modellieren lassen.

Auch Spaltengenerierungsmethoden in der linearen Optimierung benutzen h¨ aufig das K¨ urzeste-Wege-Problem mit Nebenbedingung als Unterproblem. Dieser Fall tritt zum Beispiel im Scheduling-Bereich oder auch bei komplexen Flußproblemen auf. Sowohl L¨ ubbecke und Zimmermann [13] in ihrer Betrachtung der Umlaufplanung im G¨ uterverkehr bei Werks- und Industriebahnen als auch Bornd¨ orfer und L¨ obel [4] bei ihrer Arbeit ¨ uber Terminplanung im Personenverkehr greifen darauf zur¨ uck.

Wie man sieht, gibt es eine große Anzahl von Situationen, in denen eine Nebenbedingung zus¨ atzlich zu der zu minimierenden Komponente auftritt.

1.2 Das CMCF Route-Guidance-Projekt an der TU Ber-

lin

Navigationssysteme, die einfach f¨ ur jeden Wagen den k¨ urzesten Weg von Startzu Zielort berechnen, haben den fundamentalen Nachteil, dass sie nicht die Auswirkungen ihrer eigenen Routenwahl auf das Verkehrsnetz betrachten. Aus diesem Grund funktioniert ein solches System nur, solange es von einer kleinen Zahl von Fahrern benutzt wird; denn sollte eine zu große Anzahl von Autos denselben schnellen Weg benutzen, so w¨ urde auf dieser Straße schon bald ein Stau entstehen, der diesen Vorteil zunichte machen w¨ urde. Wie Beccaria und Bolelli [3] vorschlagen, ist es also ratsam, ein System zu entwickeln, welches die Verkehrsnetzbelastung minimiert, aber gleichzeitig die individuellen Routen f¨ ur jeden Fahrer ertr¨ aglich h¨ alt. Diese Nebenbedingung ist wichtig, da es sich bei von Navigati- onssystemen errechneten Wegen nur um Vorschl¨ age handelt und sich kaum ein

KAPITEL 1. EINLEITUNG 3

Fahrer freiwillig auf eine f¨ ur ihn inakzeptable Route einlassen w¨ urde, nur weil es der Gesamtheit des Verkehrsflusses n¨ utzt. In diesem Projekt wird dies durch eine L¨ angenbeschr¨ ankung f¨ ur jeden berechneten Weg umgesetzt, d.h. jede Route darf nur um eine vorgebene Prozentzahl gr¨ oßer als der bez¨ uglich der L¨ ange optimale Weg sein.

Tabelle 1.1: Einbettung des ressourcenbeschr¨ ankten K¨ urzeste-Wege-Problems in das Hauptproblem beim CMCF-Projekt

Das ressourcenbeschr¨ ankte K¨ urzeste-Wege-Problem wird somit zu einem Teilproblem des sogenannten Constrained Multi-Commodity Flow Problems (CMCF), welches w¨ ahrend des Programmablaufs wiederholt aufgerufen wird. Genau genommen wird dabei eine Adaptation des sogenannten Frank-Wolfe-Algorithmus angewendet. Das Ausgangsproblem wird linearisiert und daraufhin mit dem Sim-plex-Algorithmus f¨ ur lineare Optimierungsprobleme bearbeitet. Da dabei exponentiell viele Variablen entstehen, werden diese nicht alle gespeichert, sondern bei Bedarf mit der Spaltengenerierungsmethode erzeugt. Wie bereits erw¨ ahnt, wird dabei das K¨ urzeste-Wege-Problem mit Nebenbedingung als Unterproblem aufgerufen.

Als L¨ osungsansatz wird hier bisher eine mit einigen Beschleunigungsmethoden versehene Erweiterung des Dijkstra-Algorithmus verwendet. Jahn, M¨ ohring und Schulz [10] stellen fest, dass bei der derzeitigen Implementation rund 95% des Gesamtaufwands mit der Ermittlung dieser Wege verbracht werden; ein besserer Algorithmus w¨ urde also zu großen Zeitersparnissen f¨ uhren.

1.3 Das CNOP-Paket

Das Constrained Network Optimization Package wurde an der Universit¨ at des Saar-landes in Saarbr¨ ucken entwickelt. Es behandelt Optimierungsprobleme in Netzwerken, welche durch die Einf¨ uhrung einer Ressourcenbeschr¨ ankung nicht mehr in polynomialer Zeit l¨ osbar sind. Diese werden in einem ersten Schritt durch obere und untere Schranken approximiert, bevor aus dem ¨ ubriggebliebenen Bereich die

L¨ osung ermittelt wird. Es werden hierbei mehrere Problemstellungen betrachtet; neben dem Table Layout Problem, Kurvenapproximationen und der Suche nach einem kostenminimalen aufspannenden Baum mit Nebenbedingung wird auch hier auf ein Routenplanungsmodell eingegangen, welches das ressourcenbeschr¨ ankte K¨ urzeste-Wege-Problem beinhaltet. Das verwendete Modell ist relativ simpel, so dass sich das f¨ ur diese Arbeit relevante Teilproblem auch autonom ausf¨ uhren l¨ asst, was den Vergleich mit anderen Implementationen erleichtert.

4

Ziegelmann [21] hat sowohl f¨ ur die Ermittlung der Schranken als auch f¨ ur das darauffolgende Suchen der Optimall¨ osung mehrere Algorithmen miteinander verglichen und hat schließlich mit seinen besten Ans¨ atzen bei selbst durchgef¨ uhrten Tests sehr gut abgeschnitten. Es bleibt jedoch die Frage, ob dieses Verfahren generell zu sehr schnellen Resultaten f¨ uhrt oder ob es f¨ ur gewisse Situationen wie zum Beispiel dem Einsatz als Unterprogramm im CMCF-Projekt ungeeignet ist.

1.4 Anforderungen an die Probleml¨ osungen

Hauptziel der vorliegenden Arbeit ist es letztlich zu untersuchen, ob ein schnellerer L¨ osungsansatz f¨ ur das ressourcenbeschr¨ ankte K¨ urzeste-Wege-Problem zu einer sp¨ urbaren Reduzierung der Gesamtlaufzeit beim CMCF-Projekt f¨ uhren kann. Um dies zu ermitteln, vergleichen wir unsere neu erstellten Algorithmen mit den in den letzten beiden Abschnitten vorgestellten Ans¨ atzen. Voraussetzung daf¨ ur ist jedoch, dass alle Verfahren genau das gleiche Problem l¨ osen. Deswegen sollten unsere Methoden den Anforderungen der vorgestellten Routenplanungssysteme gen¨ ugen.

Da die Applikation des CNOP-Pakets eher einfach aufgebaut ist, sind f¨ ur diesen Fall keine zus¨ atzlichen Bedingungen zu beachten. Gesucht wird ein bez¨ uglich einer Kostenkomponente minimaler Weg zwischen zwei Punkten, der hinsichtlich einer anderen Kostenart eine vorgegebene Schranke nicht ¨ uberschreitet.

Komplexer sieht es beim CMCF-Problem aus. Hier wird nicht nur der kostenminimale ressourcenbeschr¨ ankte Weg gesucht, sondern es reicht teilweise auch, wenn er f¨ ur beide Kostenarten unter vorgegebenen Schranken liegt. Ein hinsichtlich einer Komponente optimierter Weg w¨ urde zwar diese Bedingung erf¨ ullen, jedoch kann man davon ausgehen, dass dessen Ermittlung mit einem zeitlichen Mehraufwand verbunden sein d¨ urfte.

Zus¨ atzlich zu dieser Anforderung besitzen einige der neu erstellten Algorithmen die Eigenschaft, eine gewisse Anzahl an effektiven Wegen zu ermitteln, wobei die Effektivit¨ at darin besteht, dass ein Weg, der hinsichtlich der ersten Komponente etwas schw¨ acher ist, daf¨ ur einen g¨ unstigeren Wert bez¨ uglich der zweiten Komponente vorzuweisen hat. Dies ist zum Beispiel f¨ ur Fragestellungen von Interesse, in denen mehrere alternative Wegvorschl¨ age ben¨ otigt werden.

Somit ergeben sich drei verschiedene Problemstellungen f¨ ur diese Arbeit:

¯ Berechnung eines bez¨ uglich einer Kostenkomponente minimalen Weges bei Einhaltung einer oberen Schranke f¨ ur eine zweite Komponente

¯ Berechnung eines Weges, der bez¨ uglich beider Komponenten unterhalb der vorgegebenen Schranken liegt

¯ Berechnung mehrerer gleichermaßen effektiver Wege, die allesamt unterhalb einer vorgegebenen Schranke f¨ ur eine Kostenart liegen

KAPITEL 1. EINLEITUNG 5

Da versucht werden soll, den f¨ ur das klassische K¨ urzeste-Wege-Problem mit nichtnegativen Kantengewichten normalerweise benutzten Dijkstra-Algorithmus so zu erweitern, dass diese drei Probleme effizient gel¨ ost werden, gehen wir im folgenden Kapitel zun¨ achst auf grundlegende Eigenschaften des Algorithmus von Dijkstra ein und beschreiben f¨ ur ihn einige Beschleunigungsm¨ oglichkeiten, bevor wir die zur Erweiterung ben¨ otigten Schritte erl¨ autern.

Kapitel 2

Beschleunigungsmethoden f ¨ ur

das K ¨ urzeste-Wege-Problem mit

nicht-negativen Kantengewichten

Im folgenden Kapitel werden einige f¨ ur den weiteren Verlauf der Arbeit relevante Eigenschaften des K¨ urzeste-Wege-Problems zusammengetragen. Zus¨ atzlich zur allgemeinen Problemstellung und zum Dijkstra-Algorithmus wird auch auf m¨ ogliche Beschleunigungsmethoden zur Ermittlung der L¨ osung eingegangen.

2.1 Problemstellung

Ein Verkehrsnetz l¨ asst sich als ein gerichteter Graph modellieren, indem man jede Straße als Kante und jede Kreuzung als Knoten darstellt. Weist man nun jeder Kante einen Kostenwert zu, so entspricht die Suche nach dem g¨ unstigsten Weg zwischen zwei Orten der Ermittlung des k¨ urzesten Weges zwischen zwei Knoten auf dem erstellten Graphen.

Sei also ein gerichteter Graph G ´ V Eµ gegeben, und f¨ ur jede Kante e ¾ E exi-

stiere ein nicht-negatives Kantengewicht c e . Dann l¨ asst sich das K¨ urzeste-Wege-Problem von einem gegebenen Knoten s ¾ V zu einem gegebenen Knoten t ¾ V schreiben als min ∑

Da wir uns auf den Fall mit nicht-negativen Kantengewichten beschr¨ anken, stellen wir nun den Dijkstra-Algorithmus vor, der die Standardmethode zur L¨ osung eines solchen Problems ist.

6

KAPITEL 2. BESCHLEUNIGUNGSMETHODEN 7

2.2 Der Dijkstra-Algorithmus

2.2.1 Formulierung

Der Dijkstra-Algorithmus ist relativ simpel aufgebaut, l¨ ost das K¨ urzeste-Wege-Problem jedoch in polynomialer Zeit. In einer Initialisierungsphase wird zun¨ achst allen Knoten ein Distanzwert zugewiesen, der dem bisher gefundenen k¨ urzesten Weg vom Startknoten zum betrachteten Knoten entspricht. Somit bekommt der

Startknoten s die Distanz 0 und alle anderen Knoten bekommen die Distanz ·∞

zugewiesen. Zus¨ atzlich ben¨ otigen wir ein Vorg¨ angerarray, welches zun¨ achst f¨ ur jeden Knoten mit / 0 initialisiert wird.

In der Hauptschleife wird nun der unmarkierte Knoten v mit der kleinsten endlichen Distanz gesucht und markiert; im ersten Schritt ist dies automatisch der Startknoten. Anschließend werden alle Knoten w betrachtet, f¨ ur die eine Kante

e ´ v wµ existiert. Sollte die Distanz von w gr¨ oßer als die Distanz von v plus dem

Kantengewicht c e sein, so wird sie mit dem kleineren Wert aktualisiert, da wir damit einen g¨ unstigeren Weg zu diesem Knoten gefunden haben. Im Vorg¨ angerarray wird in diesem Fall dem Knoten w der Knoten v zugewiesen, da dieser auf dem derzeit k¨ urzesten s-w-Weg der direkte Vorg¨ anger von w ist.

Algorithmus 1: Der Dijkstra-Algorithmus

Der Algorithmus terminiert, sobald entweder der Zielknoten t markiert, also der k¨ urzeste Weg gefunden ist, oder aber kein unmarkierter Knoten mit endlicher Distanz mehr existiert. In diesem Fall gibt es keinen Weg von s nach t. Falls eine L¨ osung gefunden wird, so l¨ asst sich anhand des Vorg¨ angerarrays der k¨ urzeste s-t- Weg ermitteln.

8

2.2.2 Korrektheit und Laufzeit

Die Korrektheit des Algorithmus basiert auf folgender Festellung:

Satz 2.1. Ist ein Knoten v markiert, so entspricht die ihm zugewiesene Distanz dem k¨ urzesten Weg vom Startknoten nach v.

Beweis. Wir f¨ uhren einen Beweis durch Widerspruch aus. Sei also v ¾ V ÒÒs der erste Knoten, auf den diese Eigenschaft nicht zutrifft. Dann gibt es einen Weg

p ´ s u vµ, dessen L¨ ange kleiner als dist´vµ ist. W¨ aren alle Knoten auf

diesem Weg bereits markiert, so h¨ atte v diese L¨ ange als Distanzwert bekommen; es muss also mindestens ein unmarkierter Knoten vorhanden sein. Sei u der erste unmarkierte Punkt auf der Wegstrecke.

Der Distanzwert von u kann nur noch von einem ¨ uber einen bisher unmarkierten

Knoten f¨ uhrenden Weg verringert werden. Da jedoch gerade v markiert worden ist, w¨ urde kein solcher Weg eine kleinere L¨ ange als der bisherige Distanzwert von u erreichen. Somit muss der Distanzwert von u schon der L¨ ange δ´s uµ des k¨ urzesten

Weges von s nach u entsprechen. Es gilt also:

dist´uµ µ δ´s uµ δ´s vµ dist´vµ

Wir haben jedoch gerade v als kleinsten unmarkierten Distanzwert ermittelt, woraus ein Widerspruch folgt.

Da der Algorithmus abbricht, wenn der Zielknoten markiert ist, folgt aus dem Satz unmittelbar:

Korollar 2.2. Der Dijkstra-Algorithmus arbeitet korrekt und terminiert.

Es ergibt sich hieraus auch eine andere f¨ ur den weiteren Verlauf der Arbeit wichtige Folgerung:

Korollar 2.3. L¨ asst man den Dijkstra-Algorithmus solange weiterlaufen, bis kein unmarkierter Knoten mit endlicher Distanz mehr existiert, so entsprechen die ermittelten Distanzen f¨ ur jeden markierten Knoten v ¾ V dem k¨ urzesten Weg vom Startknoten zu ihm. Zu allen bei Programmende unmarkierten Knoten gibt es keinen Weg vom Startknoten aus.

Dies bedeutet, dass die Berechnung aller k¨ urzesten Wege von einem Startknoten aus eine Laufzeit gleicher Gr¨ oßenordnung wie die Berechnung eines k¨ urzesten Weges von einem Start- zu einem Zielknoten hat.

Generell h¨ angt die Laufzeit von der bei der Implementierung verwendeten Datenstruktur zur Verwaltung der unmarkierten Knoten und ihrer Distanzen ab. Wie in Tabelle 21 zu sehen ist, ist die Laufzeit aber polynomial.

KAPITEL 2. BESCHLEUNIGUNGSMETHODEN 9

Tabelle 2.1: Aufwand des Dijkstra-Algorithmus bei Verwendung verschiedener Datenstrukturen

2.3 Beschleunigungsmethoden f ¨ ur den Dijkstra-Ansatz

Wie im vergangenen Abschnitt beschrieben wurde, ist der Dijkstra-Algorithmus im Grunde genommen darauf spezialisiert, k¨ urzeste Wege von einem Start- zu mehreren Zielknoten zu berechnen. M¨ ochte man nur den Weg zu einem bestimmten Knoten berechnen, so ¨ andert sich der eigentliche Verlauf des Verfahrens nicht. Weiterhin breitet sich der Dijkstra-Algorithmus mehr oder weniger kreisf¨ ormig vom Startknoten aus, um in alle Richtungen k¨ urzeste Wege zu erstellen, unabh¨ angig davon, wo sich der Zielknoten befindet.

Um die Suche effizienter zu gestalten, scheint es also naheliegend, sich Methoden zu ¨ uberlegen, welche entweder zus¨ atzlich vom Zielknoten aus operieren oder sich etwas zielgerichteter in dessen Richtung verbreiten. M¨ oglicherweise l¨ asst sich der sich auf diese Weise ergebende Beschleunigungseffekt noch weiter verst¨ arken, wenn beide Ideen miteinander kombiniert werden.

10

2.3.1 Der zielgerichtete Ansatz

Der zielgerichtete Ansatz versucht, den k¨ urzesten Weg schneller zu finden, indem er Teilwege, die offensichtlich zu einem langem s-t-Weg f¨ uhren, nicht weiter betrachtet. Dies wird erreicht, indem die Kantengewichte transformiert werden, so dass genau die Kanten, welche in die Richtung des Zielknotens f¨ uhren, vom Algorithmus bevorzugt werden, w¨ ahrend solche, die in die entgegengesetzte Richtung laufen, mit einem ung¨ unstigeren Kostenwert bestraft werden.

Abbildung 2.2: Transformation der Kantengewichte.

Zur korrekten Ausf¨ uhrung werden untere Schranken LB ´vtµ f¨ ur die k¨ urzesten Wege von allen Knoten v ¾ V zum Zielknoten t ben¨ otigt. Die folgenden modifizierten Kantenbewertungen werden dann benutzt:

: c ´vwµ   LB ´vtµ ·LB ´wtµ c ¼

(2.1)

´vwµ

Wie wir in Abbildung (2.2) gut erkennen k¨ onnen, wird somit der gew¨ unschte Ef-

fekt erreicht. Die Kante ´vw 1 µ wird gegen¨ uber ´vw 2 µ bevorzugt behandelt, da die

untere Schranke f¨ ur den restlichen w 1 -t-Weg kleiner als LB´w 2 tµ ist.

Der Dijkstra-Algorithmus funktioniert wie bereits erw¨ ahnt nur f¨ ur nicht-negative Kantengewichte. M¨ ochte man deswegen das Verfahren mit den transformierten Kantenkosten benutzen, so muss f¨ ur die unteren Schranken folgende Konsistenzbedingung gelten:

c ´vwµ ·LB ´wtµ LB ´vtµ

(2.2)

KAPITEL 2. BESCHLEUNIGUNGSMETHODEN 11

Diese Eigenschaft wird von vielen Bewertungsfunktionen erf¨ ullt. Bei der Suche nach einem Weg mit der k¨ urzesten L¨ ange w¨ are zum Beispiel der geographische Abstand zwischen den jeweiligen Knoten als untere Schranke benutzbar.

Wenden wir nun den Dijkstra-Algorithmus auf die neuen Kantengewichte an, so

liefert er einen k¨ urzesten s-t-Weg der L¨ ange dist ¼ ´tµ. Es l¨ asst sich zeigen, dass dies

auch der k¨ urzeste Weg bez¨ uglich der urspr¨ unglichen Kosten dist´tµ ist. Satz 2.4. Seien auf einem Graphen G ´ V Eµ f¨ ur Wege von jedem Knoten v zum

Zielknoten t untere Schranken LB´vtµ gegeben, die die Konsistenzbedingung (2.2) erf¨ ullen. Wird der Dijkstra-Algorithmus mit anhand der Transformation (2.1) modifizierten Kantengewichten gestartet, so ist die ermittelte L¨ osung ein k¨ urzester st-Weg bez¨ uglich der urspr¨ unglichen Kantengewichte, und f¨ ur die Kosten des Weges gilt:

dist´tµ µ dist ¼ ´tµ · LB ´stµ   LB ´ttµ

Beweis. Sei p ´ s v 1 v 2 v n tµ ein s-t-Weg. F¨ ur seine L¨ ange gilt:

dist ¼ ´tµ c ¼ ·c ¼ · ·c ¼

Die L¨ ange eines s-t-Weges unterscheidet sich also bei Benutzung der modifizierten Kantengewichte nur um einen kostanten Wert von der urspr¨ unglichen Wegl¨ ange. Daraus folgt, dass der ermittelte k¨ urzeste s-t-Weg auch ein k¨ urzester Weg bez¨ uglich des Ausgangsproblems sein muss.

Algorithmus 2: Der zielgerichtete Dijkstra-Ansatz