A Practical Guide to Data Structures and Algorithms using Java

Abstract Weighted Graph and Weighted Graph Algorithms 935

WeightedGraph

cost, and (2) that the cost associated with each vertex v ∈ Q is the cost of the minimum cost

extension of T by v. More formally,

• ∀v ∈ T, v

cost

= d(v), and

• ∀v ∈ Q, v

cost

is the value of the minimum cost extension of T by v.

Base: Initially T = ∅, and Q = {s} for which s

cost

= d(s) = 0. So both invariants initially

hold.

Inductive step: Assume that when |T | = i, both invariants hold. We now prove that the invari-

ants are preserved when the next vertex is added to T. Let v be the (i + 1)

st

vertex extracted

from the priority queue, and hence implicitly moved from Q to T , and let