Shortest Path Reduction1st attempt

v and w are both redundant

Removal of one depends on presence

of other.

Idea

Problem

w

<=w

An edge is REDUNDANT if there exists

an alternative path of no greater weight

THUS Remove all redundant edges!

w

v

Observation: If no zero- or negative

cycles then SAFE to remove all

redundancies.

Previous slide

Next slide

Back to first slide

View graphic version