Go up to Top Go forward to Example

A Graph-Theoretical Problem

• 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$