Entwurf und Implementierung eines Routing-Algorithmus und eines zugrundeliegenden Datenmodells am Beispiel des Straßennetzes

Inhaltsverzeichnis

Aufgabenstellung

Danksagung

1 Einleitung
1.1 Zielsetzung der Arbeit
1.2 Aufbau der Arbeit

2 Erläuterung von Bezeichnungen und Begriffen
2.1 Graphentheorie
2.1.1 Euler und Hamilton
2.1.2 Bäume
2.1.2.1 Minimaler Spannbaum
2.1.2.2 1-Baum
2.2 Komplexitätstheorie
2.2.1 Komplexität von Algorithmen
2.2.2 NP-Probleme

3 Einführung in Routing-Probleme
3.1 Kürzeste-Wege-Problem
3.1.1 Dijkstra-Algorithmus
3.1.2 A*-Algorithmus
3.1.3 Floyd-Warshall-Algorithmus
3.1.4 Abbiegeverbote
3.1.4.1 Kantenaufnahme
3.1.4.2 Mehrfache Knotenaufnahme
3.1.4.3 Ziehen neuer Kanten
3.1.4.4 Verbotsorientiertes Knotensplitting
3.1.4.5 Knotenorientierte Netzwerke
3.1.5 Wegeverbote
3.1.6 Kürzeste Wege in modifizierten Graphen
3.2 Chinesisches-Postboten-Problem
3.3 Traveling-Salesman-Problem
3.3.1 Bestimmung einer oberen Schranke
3.3.2 Bestimmung einer unteren Schranke
3.3.3 Branch-and-Bound-Verfahren

4 Implementierung eines Systems zur Routenplanung
4.1 Datenmodell
4.2 Demonstrator

5 Zusammenfassung und Ausblick

Literaturverzeichnis

Abbildungsverzeichnis

Aufgabenstellung

Abbildung in dieser Leseprobe nicht enthalten

Danksagung

An dieser Stelle möchte ich allen danken, die einen Teil zum Gelingen dieser Arbeit beigetragen haben.

Ich bedanke mich bei Herrn Prof. Dr.-Ing. Franz Josef Lohmar für das Ermöglichen dieser Diplomarbeit durch die interessante Aufgabenstellung, für die hilfreichen Gespräche und die sonstige Betreuung.

Bei Herrn Prof. Dr.-Ing. Manfred Bäumker bedanke ich mich für die Übernahme der Aufgabe des Korreferenten.

Des Weiteren möchte ich mich bei Herrn Sebastian Bönigk für die Hilfe bei der Erzeugung einer Datenbank-Schnittstelle bedanken.

Ein besonderer Dank geht an meine Mutter, die mir nach dem Defekt meines Notebooks ihren PC-Arbeitsplatz zur Verfügung gestellt hat, sowie an meine gesamte Familie für die Motivation während des Studiums und den finanziellen Rückhalt.

1 Einleitung

Mobilität und Wirtschaftlichkeit haben in unserer Gesellschaft einen hohen Stellenwert. Hierzu gehört unter anderem, möglichst zeit- oder kostengünstig ein geografisches Ziel zu erreichen. Dabei spielt der Einsatz von Systemen zur Routenplanung und –führung eine sehr große Rolle. Der technische Fortschritt der letzten Jahre hat dazu geführt, dass nicht nur in vielen Kraftfahrzeugen Navigationssysteme zur Standardausstattung gehören, sondern dass es auch leistungsstarke Lösungen zur Zielführung gibt, die in mobilen Geräten wie etwa in Personal Digital Assistant’s (PDA’s) integriert sind. Auch im Internet sind Routenplaner verfügbar, die für jeden Benutzer kostenfrei den optimalen Weg zu einem beliebigen Ziel in ganz Europa ermitteln.

Die Grundlage für derartige Systeme, die effizient einen optimalen Weg bestimmen, liegt in der möglichst präzisen Abbildung der Wirklichkeit in einem Datenmodell, ohne jedoch überflüssige Daten zu erheben. Anschließend muss auf diese Daten ein der Problemstellung angepasster Algorithmus angewendet werden, der in annehmbarer Zeit ein Ergebnis liefert.

Das Gebiet der Routenplanung umfasst aber noch mehr Fragestellungen, als nur Die nach dem kürzesten Weg zu einem gegebenen Ziel. Weitere Problemstellungen sind beispielsweise die Suche nach einer möglichst günstigen Verbindung mehrerer Orte, wie etwa für eine Geschäftsreise, oder auch die Suche nach einer effizienten Tour für die Müllabfuhr, also einer Route, auf der jede Straße eines Bezirks mindestens einmal, aber möglichst wenige Straßen doppelt befahren werden.

1.1 Zielsetzung der Arbeit

Im Fachbereich Vermessung und Geoinformatik der Hochschule Bochum, in dem diese Arbeit entstanden ist, sind bisher keine Forschungen zu dem Thema Routenplanung gelaufen. Aus diesem Grund ist dieses Werk in gewisser Weise als Pionierarbeit zu sehen. Ziel dieser Arbeit ist es somit, zunächst eine Einführung in diese vielfältige Problematik der Bestimmung optimaler Wege in den verschiedenen Anwendungsbereichen zu geben und die hierzu bestehenden Lösungsansätze vorzustellen. Des Weiteren soll auf der Grundlage einer selbst entworfenen Datenstruktur ein Programm implementiert werden, das das Kürzeste-Wege-Problem löst. Dieses Programm soll in der Lage sein, unter Berücksichtigung von speziellen Bedingungen, wie z.B. Abbiegeverboten, einen optimalen Weg von einem Start- zu einem Zielpunkt anzugeben. Auch die Auswahl eines Zwischenpunktes soll optional möglich sein. Die Suche eines optimalen Weges meint an dieser Stelle wahlweise den kürzesten oder den schnellsten Weg. Die Entwicklung eines komplexen und komfortablen Programms mit grafischer Ausgabe der Wegbeschreibung und vielen gängigen Extrafunktionen ist nicht vorgesehen.

1.2 Aufbau der Arbeit

Zunächst sollen die zum Verständnis dieser Arbeit notwendigen Begriffe aus der Graphentheorie und die verwendeten Bezeichnungen erläutert werden. Es wird in diesem Zusammenhang auch kurz auf die Bewertung der Zeitkomplexität von Algorithmen eingegangen. Daran anschließen soll eine Darlegung der vielen unterschiedlichen Problemstellungen der Routenplanung, Ansätze diese Aufgaben zu lösen und teilweise auch die Angabe und Erläuterung von gebräuchlichen Algorithmen. Im daran anschließenden Kapitel wird auf das von mir entwickelte und implementierte System zur Routenplanung eingegangen. Dabei wird zum Einen das zugrundeliegende Datenmodell erläutert, zum Anderen das hierauf zugreifende Programm mit den verwendeten Algorithmen.

2 Erläuterung von Bezeichnungen und Begriffen

Die Grundlage für ein funktionierendes Routenplanungssystem bildet, wie bereits erwähnt, die wirklichkeitsgetreue Abbildung des Straßennetzes. Diese Abbildung in ein mathematisches Modell erfolgt in einen Graphen. In diesem Kapitel werden die Begriffe und Bezeichnung der Graphentheorie erläutert, die für das Verständnis dieser Arbeit wichtig sind und im weiteren Verlauf Verwendung finden. Auf formal-mathematische Definitionen wird aus Gründen der Verständlichkeit jedoch verzichtet. Am Ende dieses Kapitels wird auch noch kurz auf die Komplexitätstheorie eingegangen, mit deren Hilfe die Bewertung der Laufzeit von Algorithmen durchgeführt wird.

2.1 Graphentheorie

Die Grundelemente eines Graphen G sind Knoten und Kanten. Knoten stellen als punktförmige Elemente - je nach Grad der Generalisierung - z.B. Straßenkreuzungen oder Ortschaften dar, Kanten sind linienförmige Elemente, die die Verbindungen zwischen je zwei Knoten herstellen. Die Menge aller einzelner Knoten vi wird als V bezeichnet, die Menge aller einzelner Kanten ei als E. Daraus folgt als Schreibweise für den Graphen G=(V, E). Zur Bewertung eines Graphen können sowohl die Knoten als auch die Kanten mit Gewichten versehen werden. Als Kantengewicht kann die Länge einer Kante in Kilometern oder auch die zum Passieren dieser Kante benötigte Fahrzeit in Minuten gewählt werden. Knotengewichte sind z.B. als besonders lange Wartezeit an einer Kreuzung denkbar, aber eher unüblich. An Stelle von Gewichten wird auch die Bezeichnung Kosten ki verwendet. Es ist sinnvoll und bei manchen Algorithmen sogar notwendig, nur positive Zahlen als Gewichte zu verwenden.

Ein Graph heißt zusammenhängend, wenn es möglich ist, von jedem Knoten unter Verwendung der vorhandenen Kanten zu jedem anderen Knoten zu gelangen. Ist ein Graph auch nach Wegnahme einer beliebigen Kante noch zusammenhängend, so heißt er zweifach zusammenhängend.

Es besteht die Möglichkeit, gerichtete Kanten zu verwenden. Solche Kanten haben einen Anfangs- und einen Endknoten und werden als Bögen bezeichnet. Ein Graph, der nur Bögen, aber keine Kanten mehr hat, heißt Digraph. Ein stark zusammenhängender Graph ist ein zusammenhängender Digraph (vgl. Abbildung 1). Wenn die Knoten eines Graphen sowohl durch Kanten, als auch durch Bögen miteinander verbunden werden, spricht man von einem gemischten Graphen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: zusammen-hängender Digraph

Es kann vorkommen, dass ein Knotenpaar durch mehrere Kanten verbunden wird. Dieses ist z.B. bei Netzplänen der Deutschen Bahn der Fall. Ein solcher Graph heißt Multigraph. Bei einem Graphen wie dem in Abbildung 1, in dem ein Knotenpaar durch zwei gegenläufige Bögen verbunden ist, handelt es sich nicht um einen Multigraph. Eine Schleife bezeichnet eine Kante oder einen Bogen von einem Knoten auf sich selbst. Eine Folge von Bögen oder Kanten, die ohne Mehrfachnutzung eines Bogens beziehungsweise einer Kante wieder zum Anfangsknoten zurückführt, heißt Kreis. Ein Graph ist kreisfrei, wenn er ungerichtet und ohne Kreise ist. In einem vollständigen Graphen ist jeder Knoten mit jedem anderen Knoten direkt verbunden.

Mit dem Grad oder der Wertigkeit eines Knotens bezeichnet man die Anzahl der Bögen beziehungsweise der Kanten, die diesen Knoten enthalten. Bei Bögen gibt es eine weitere Unterscheidung zwischen den Bögen, die in einen Knoten münden (Ingrad) und Bögen, die von einem Knoten ausgehen (Ausgrad). Der Grad eines Knotens wird zur Formulierung einer wichtigen Eigenschaft von Graphen verwendet, nämlich der, dass jeder Graph eine gerade Anzahl von Knoten ungerader Wertigkeit besitzt. Diese Eigenschaft lässt sich einfach beweisen, indem zunächst ein Graph ohne Kanten gegeben sei. Somit haben alle Knoten eine gerade Wertigkeit, nämlich null. Das Ziehen der ersten Kante führt bei zwei Knoten zu der ungeraden Wertigkeit eins. Wird nun zwischen zwei Knoten geraden Grades eine Kante gezogen, so steigt die Anzahl der Knoten ungeraden Grades um zwei, analog sinkt Diese um zwei beim Ziehen einer Kante zwischen zwei Knoten ungeraden Grades. Eine Kante zwischen einem Knoten ungeraden Grades und einem Knoten geraden Grades ändert nichts an der Anzahl von Knoten ungeraden Grades. Somit ändert sich die Anzahl der Knoten ungerader Wertigkeit begonnen bei null entweder um zwei oder gar nicht, bleibt also immer gerade.

2.1.1 Euler und Hamilton

Ein Mathematiker, der sich unter anderem mit der Graphentheorie beschäftigt und sie in gewisser Weise begründet hat, ist Leonhard Euler. Aus diesem Grund tragen einige Begriffe in diesem Bereich seinen Namen: Als Eulerweg wird jeder Weg durch einen Graphen bezeichnet, der von einem Startknoten ausgehend jede Kante genau einmal benutzt. Als Eulerkreis wird ein Eulerweg bezeichnet, der in seinem Startknoten endet. Dem entsprechend wird mit Eulerkreis-Problem die Aufgabe bezeichnet zu prüfen, ob es in einem Graphen einen Eulerkreis gibt und diesen anzugeben. Falls ein Graph einen Eulerkreis enthält, so heißt er eulersch. Unter Ausnutzung des Grades eines Knotens lässt sich der Satz von Euler aufstellen, der besagt, dass für jeden zusammenhängenden Graphen ein Eulerweg existiert, wenn höchstens zwei Knoten ungerade Wertigkeit besitzen und dass ein Eulerkreis genau dann existiert, wenn alle Knoten gerade Wertigkeit besitzen.

Für eine weitere sehr bedeutende Problemstellung ist der irische Astronom und Mathematiker Sir William Rowan Hamilton der Namensgeber. Zur Beschreibung dieser Aufgabe gibt es, analog zu dem Eulerweg und –kreis, den Hamiltonweg und –kreis. Ein Hamiltonweg ist jeder Weg durch einen Graphen, der von einem Startknoten ausgehend jeden Knoten genau einmal benutzt. Der Hamiltonkreis ist ein Hamiltonweg, der in seinem Startknoten endet. Die Suche nach einem Hamiltonkreis in einem Graphen wird als Hamiltonkreis-Problem bezeichnet.

2.1.2 Bäume

Eine weitere Gruppe von Graphen, auf die kurz eingegangen werden soll, ist die der Bäume. Ein Baum ist ein kreisfreier, zusammenhängender Graph. Den Knoten am Beginn eines Baumes nennt man Wurzel, die Endknoten eines Baumes heißen Blätter (vgl. Abbildung 2). Bäume spielen in der Graphentheorie eine große Rolle. Sie bilden innerhalb eines Graphen sowohl eine maximale, kreisfreie Teilmenge als auch eine minimale zusammenhängende Teilmenge. Jedes Hinzufügen einer Kante würde zu einem Kreis führen und jede Wegnahme einer Kante würde den Baum in zwei Teile teilen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Baum

2.1.2.1 Minimaler Spannbaum

Ein Spannbaum ist ein Baum, der alle Knoten eines Graphen miteinander verbindet. Ist der Spannbaum minimal, so erzeugt er die geringsten Kosten. Anders ausgedrückt ist die Summe der Gewichte der für den Spannbaum gewählten Kanten minimal. Zum Erzeugen minimaler Spannbäume ist es wichtig, immer nur die günstigsten Kanten auszuwählen. Algorithmen, die derartig vorgehen, werden als Greedy-Algorithmen bezeichnet. Dieser Name stammt von dem englischen Wort greedy (deutsch: gierig), da solche Algorithmen immer „gierig“ nach den günstigsten Kanten greifen. Ein solcher Algorithmus ist beispielsweise der Prim-Algorithmus, dessen Funktionsweise im Folgenden erläutert werden soll. In den nebenstehenden Abbildungen werden die erreichten Knoten des Beispielgraphen rot gefärbt, die gewählten Kanten schwarz, die als nächstes auswählbaren Kanten grün und der Rest des Graphen wird in grau dargestellt. Der Prim-Algorithmus wählt als erste Kante die aus, die den Startknoten am günstigsten verlässt. Dies ist im Beispiel die Kante von s nach a mit dem Gewicht 3. Im nächsten Schritt wird die Kante gewählt, die den Startknoten oder den soeben erreichten Knoten am günstigsten verlässt. Die nun gewählte Kante ist die von Knoten a nach b mit dem Gewicht 1. In diesem Schritt wird außerdem die Kante von s nach b aus dem Graphen gelöscht, da die Auswahl dieser Kante einen für Bäume unzulässigen Kreis erzeugen würde. Die Strategie ist also, unter allen Kanten, die die erreichten Knoten verlassen, die insgesamt Günstigste zu wählen, wobei jedoch Kreise zu vermeiden sind. Als Ergebnis liefert dieser Algorithmus den in Abbildung 4 dargestellten minimalen Spannbaum. Dieser Algorithmus wurde zur detaillierteren Beschreibung ausgewählt, da er dem in Kapitel 3.1.1 beschriebenen Dijkstra-Algorithmus zur Bestimmung kürzester Wege sehr ähnlich und somit durch eine leichte Modifikation hieraus ableitbar ist. In Abbildung 5 ist der Prim-Algorithmus dargestellt, die Änderungen gegenüber dem Dijkstra-Algorithmus sind rot hervorgehoben.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5: Prim-Algorithmus

Ein weiteres Verfahren aus der Gruppe der Greedy-Algorithmen, das an dieser Stelle nur nachrichtlich erwähnt wird, ist der Kruskal-Algorithmus. Während der Prim-Algorithmus nur die von erreichten Knoten abgehenden Kanten betrachtet, sucht der Kruskal-Algorithmus immer die im gesamten Graphen günstigste Kante. Es ist jedoch auch hier darauf zu achten, dass Kanten, die einen Kreis erzeugen würden, aus dem Graphen entfernt werden, damit sie nicht ausgewählt werden können. Auch dieser Algorithmus liefert als Ergebnis einen minimalen Spannbaum.

2.1.2.2 1-Baum

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6: 1-Baum

Ein ganz besonderer Baum ist der 1-Baum (sprich Einsbaum). Um einen 1-Baum zu erhalten, muss man zunächst einen beliebigen Knoten mit seinen abgehenden Kanten aus dem Graphen entfernen und aus dem verbleibenden Graphen einen minimalen Spannbaum bestimmen. Anschließend wird der minimale Spannbaum um den zuvor entfernten Knoten mit seinen beiden günstigsten Kanten ergänzt. In Abbildung 6 ist ein 1-Baum dargstellt. Hierbei sind die grünen Kanten die für den minimalen Spannbaum gewählten, die roten Kanten und der mit einer 1 versehene Knoten wurden zu Beginn entfernt und zum Schluss wieder angefügt. Die Zahlen an den Kanten sind die Kantengewichte. Der 1-Baum wird bei der Bestimmung von Rundreisen eine Rolle spielen.

2.2 Komplexitätstheorie

Zum Abschluss dieses Kapitels soll kurz auf die Bewertung von Algorithmen eingegangen werden. Hierzu ist es nötig, sich mit der Komplexitätstheorie auseinander zu setzen. Die Komplexitätstheorie ist ein Teilgebiet der theoretischen Informatik, das sich eben mit dieser Problematik beschäftigt. Zur Bewertung algorithmisch behandelbarer Probleme werden zunächst mathematische Modelle von Rechnern aufgestellt. Dies ist notwendig, um Algorithmen unabhängig von der Leistungsstärke des jeweiligen Computers bewerten und vergleichen zu können. Anschließend wird ein Vergleichsmaßstab festgelegt, wie etwa der Speicherplatzbedarf oder die Rechenzeit.

2.2.1 Komplexität von Algorithmen

Im Folgenden soll auf das wohl wichtigste Modell, die Turing Maschine, eingegangen werden. Die Turing Maschine wurde 1937 von dem britischen Mathematiker, Logiker und Kryptoanalytiker Alan Mathison Turing entwickelt. Das Besondere an diesem Modell ist, dass es hierdurch möglich wird, die Laufzeit eines Algorithmus auf die Anzahl weniger Grundoperationen zurückzuführen. Diese Grundoperationen sind die Grundrechenarten Addition, Subtraktion, Multiplikation und Division sowie die Vergleichsoperationen kleiner, größer und gleich und die Zuweisung eines Wertes. Zur Ermittlung der Laufzeit wird die Anzahl der durchzuführenden Grundoperationen beim Durchlaufen des Algorithmus bestimmt. Hierbei ist es nicht wichtig, die genaue Anzahl festzustellen, sondern vielmehr wird eine obere Schranke als Wert festgelegt, der unterschritten oder maximal erreicht, nie aber überschritten wird. Da es sich um die Bestimmung einer oberen Schranke handelt, wir als Symbol der Buchstabe O verwendet. Die Anzahl der ermittelten Grundoperationen wird bei Routenplanungsproblemen je nach Algorithmus in Verhältnis zur Anzahl der im Graphen vorkommenden Knoten oder Kanten bewertet. Sind beispielsweise bei einem Graphen mit n Knoten n2 Grundoperationen notwendig, so wird diese Komplexität dargestellt als O(n2) und man sagt, der Algorithmus hat eine quadratische Laufzeit in n. Diese grobe Einteilung der Algorithmen soll nur ein erstes Qualitätsmerkmal sein. Deshalb genügt es, bei der Anzahl der durchzuführenden Grundoperationen nur den höchsten Exponenten zu betrachten. So wird z.B. die Menge von 2*n3+n2+1000*n Grundoperationen als O(n3) eingestuft [Komplexität].

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 7: Laufzeit von Algorithmen

In Abbildung 7 sind die Laufzeiten unterschiedlicher Komplexitäten unter der Annahme dargestellt, dass in einer Sekunde 1000000 Grundoperationen durchgeführt werden. Bei Betrachtung der Laufzeit des Algorithmus mit n2+2000*n wird deutlich, dass der Anteil von 2000*n an der Laufzeit im Vergleich zu n2 mit steigender Knotenanzahl immer geringer wird und somit eine Beschränkung auf den höchsten Exponenten ausreichend ist. Eine detaillierte Bestimmung der durchzuführenden Grundoperationen wird im Kapitel 3.1.1 für den Dijkstra-Algorithmus durchgeführt.

2.2.2 NP-Probleme

In der Komplexitätstheorie beschäftigt man sich nicht nur mit der Frage, in welcher Zeit ein Algorithmus durchlaufen wird, sondern auch mit der Frage, ob eine algorithmische Behandlung überhaupt möglich ist. Ein Entscheidungsproblem ist in der theoretischen Informatik ein Problem, zu dem es nur zwei Antworten gibt, z.B. „0“ und „1“ oder „ja“ und „nein“. Wenn es für ein Entscheidungsproblem, zu dem die Antwort „ja“ lautet, automatisch einen effizient überprüfbaren Beweis gibt, so nennt man dieses ein NP-Problem. NP bedeutet hierbei nichtdeterministisch polynomial. Als Beispiel sei zu einem beliebigen Graphen die Frage gestellt, ob dieser Graph eulersch ist. Lautet die Antwort „ja“, so ist als Beweis von jedem Knoten die jeweilige Wertigkeit zu überprüfen. Diese Antwort ist also effizient überprüfbar. Es gibt aber auch eine Reihe von Problemen von so großer Schwierigkeit, dass automatisch alle NP-Probleme gelöst wären, wenn es einen effizienten Algorithmus für eines dieser Probleme gäbe. Derartige Probleme werden als NP-schwer bezeichnet. Für NP-schwere Probleme gibt es bislang keine effizienten Algorithmen – und vermutlich wird es sie auch nie geben [Gritzmann].

3 Einführung in Routing-Probleme

In diesem Kapitel sollen die verschiedenen Routing-Probleme vorgestellt werden. Für die im Demonstrator implementierten Fälle wird eine detaillierte Beschreibung der Problemstellung und dessen Lösung in Form von Algorithmen dargestellt. Die nicht implementierten Anwendungsgebiete und Sonderfälle werden zwar erwähnt, aber über eine Beschreibung der Lösungsstrategie hinweg nicht behandelt.

3.1 Kürzeste-Wege-Problem

Das im Alltag am häufigsten vorkommende Routing-Problem ist wohl das der Bestimmung kürzester Wege. Diese Aufgabe lösen selbst die einfachsten Navigationsgeräte, wodurch nahezu jeder bereits mit diesem Problem konfrontiert wurde. Da es theoretisch möglich ist, dass es in einem Graphen von einem Start- zu einem Zielknoten mehrere gleichlange kürzeste Wege gibt, spricht man nicht von dem, sondern von einem kürzesten Weg.

Bei der Suche nach einem kürzesten Weg von einem Start- zu einem Zielknoten könnte man zunächst auf die Idee kommen, einfach alle möglichen Wege auszuprobieren und sich den kürzesten herauszusuchen. Dieses Verfahren würde jedoch sehr schnell die Leistungsfähigkeit modernster Rechneranlagen übersteigen, da die Anzahl der möglichen Wege exponentiell zur Anzahl der vorhandenen Knoten steigt. Unter der Annahme, dass von jedem der n Knoten aus zwei Weitere erreichbar sind, gäbe es 20,5*n-1 Möglichkeiten, also beispielsweise bei 102 Knoten 250 mögliche Wege. Allein die Berechnung dieser 1,1 Billiarden Wege würde etwa 36 Jahre dauern. In der Mathematik wird ein derartiges Ansteigen der Möglichkeiten als kombinatorische Explosion bezeichnet. Solche Verfahren sind selbstverständlich zur Problemlösung ungeeignet [Gritzmann].

3.1.1 Dijkstra-Algorithmus

Die Standardlösung bei der Suche nach einem kürzesten Weg führt zu dem Dijkstra-Algorithmus. Dieser verfolgt die Strategie, immer nur die in einem Knoten möglichen Alternativen zu untersuchen und nicht komplette Wege durch einen Graphen. Die Suche erfolgt auch nicht zielgerichtet in Richtung des Zielknotens, vielmehr werden kürzeste Wege von dem Startknoten aus zu allen Knoten des Graphen gesucht. Hierbei kann die Suche abgebrochen werden, wenn ein kürzester Weg zu dem Zielknoten gefunden wurde. Mit den folgenden Abbildungen soll der Algorithmus näher erläutert werden. Es werden die erreichten Knoten rot gefärbt, die benutzten Kanten schwarz und die als nächstes benutzbaren Kanten grün. Der restliche Teil des Beispielgraphen wird grau gefärbt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 8: Prinzip des Dijkstra-Algorithmus

Abbildung 8 zeigt oben den Graphen, in dem ein kürzester Weg von s nach z gesucht werden soll. Im ersten Schritt wird von allen Bögen der herausgesucht, der s am günstigsten verlässt. Dies ist der Bogen nach a mit dem Gewicht 3. Der erreichte Knoten wird rot gefärbt und in den Knoten wird die Länge des Weges vom Startknoten eingetragen. Außerdem wird der Knoten s als Vorgänger des Knoten a gespeichert, um am Ende der Suche nicht nur die Länge des Weges zum Zielknoten zu kennen, sondern auch den Weg dorthin konstruieren zu können. Alle Bögen, die in s und a beginnen, werden nun grün gezeichnet, da sie als nächstes verwendet werden können. Für die jetzt erreichbaren Knoten wird jeweils aus allen möglichen Wegen der Kürzeste bestimmt und in die Knoten eingetragen. Nun wird unter allen erreichbaren Knoten der mit dem kürzesten Weg ermittelt und ausgewählt. Dies ist Knoten b, der über den Bogen von Knoten a aus erreicht wird. Dieser wird folglich als Vorgänger von b gespeichert. Der Bogen von s nach b kann gelöscht werden, da b bereits günstiger, als über diesen Bogen möglich, erreicht wurde. Im nächsten Schritt wird wieder das so genannte Update durchgeführt. Dies ist das Auswählen aller verwendbarer Bögen (hier das grün färben) und die Berechnung der kürzesten Wege zu den aktuell erreichbaren Knoten. Unter Diesen wird nun wieder der mit dem kürzesten Weg herausgesucht, Knoten c mit der Weglänge 6 von s aus und b als Vorgänger. Nach dem nächsten Update wird Knoten d mit der Weglänge 7 und dem Vorgänger b ausgewählt. So verfährt der Algorithmus, bis ein kürzester Weg zu allen Knoten beziehungsweise zum Zielknoten gefunden wurde. Das Ergebnis ist ein

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 9: kürzeste-Wege-Baum

Kürzeste-Wege-Baum. Wurde Dieser in einem Digraphen bestimmt, so nennt man ihn Arboreszenz. Abbildung 9 zeigt den Kürzeste-Wege-Baum für den Beispielgraphen, in dem kürzeste Wege zu allen Knoten gefunden wurden [Gritzmann].

[...]