Go up to
Top
Go forward to
Example
A Graph-Theoretical Problem
"All Pairs Shortest Paths"
Given: graph
G=(V,A)
Directed acyclic graph,
|V |= n
Representation: weight matrix
W
W =
0
if
i=j
w > 0
if edge of length
w
between nodes
i
and
j
infty
if no edge between
i
and
j
Wanted: distance matrix
D
D =
0
if
i=j
d > 0
if
i /=j
where
d
length of shortest path between
i
and
j
infty
if no edge between
i
and
j
Author:
Wolfgang Schreiner
Last Modification: October 13, 1997