|
|
|
|
ein bewerteter schlichter Graph mit 
für alle 
Für zwei verschiedene Knoten 
von 
wird ein kürzester Weg von 
nach
gesucht, d.h. ein Weg von
nach ,
für den die Summe der Bewertungen der Kanten
bzw. Bögen minimal ist.
mit
die Entfernungsmatrix oder
Distanzmatrix 
vom Typ 
aufstellen:
 |
(5.335) |
Sind speziell alle Kanten mit 1 bewertet, d.h. der Abstand von
und
ist gleich der
Mindestanzahl der Kanten, die man durchlaufen muß, um im Graphen von
nach
zu
gelangen, kann man den Abstand zweier Knoten aus der Adjazenzmatrix ermitteln:
Die Knoten von
seien 
Die Adjazenzmatrix von
ist 
und die Potenzen der Adjazenzmatrix
bezüglich der üblichen Multiplikation von Matrizen werden mit
bezeichnet.
Vom Knoten 
zum Knoten 
führt genau dann ein kürzester Weg der
Länge 
wenn gilt:
 |
(5.336) |
| Beispiel A | |||
|
Der in der Abbildung dargestellte bewertete Graph mit der Knotenzahl 6 besitzt die
nebenstehend angegebene Entfernungsmatrix.
| |||
| Beispiel B | ||||
|
Der in der Abbildung gezeigte ungerichtete Graph hat die dazu angegebene
Entfernungsmatrix (Adjazenzmatrix).
Für
Kürzeste Wege der Länge 
verbinden die Knoten 
und 
und 
und
und 
und 
und 
sowie 
und .
Dagegen haben kürzeste Wege zwischen den Knoten
und
und 6 bzw.
und 
die Länge  .
| ||||
|
|
bzw. 
erhält man die Matrizen
und 
aus denen man die Länge der kürzesten Wege ablesen kann,
die zwei Knoten des Graphen verbinden.
