Project Links Logo Artwork
Graph Theory: Networking
Home > Graph Theory: Networking > Foundations > Shortest Paths
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

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

 
 
go backgo forward
go backgo forward