Shortest Paths
Our next step in generalizing the notion of a graph is to consider
weighted graphs, for which every edge is
associated with a real number, called a weight
(or cost, or length) of the
edge. Weights can be negative or nonnegative.
This generalization prompts us to modify our definition of the length
of a walk, which we are going to call the weight of a walk
in order to differentiate it from the notion of the
number of edges in a walk.
Here is the formal definition of the weight of a walk:
Given a weighted directed graph
with a weight function
,
the weight
of a walk
Equation
1
is defined as the sum
Equation
2
The distance
from to is defined by
Equation
3
if no directed walk from
to
exists
is a directed walk from
to
|