Weighted Graphs (cont)
Weights lead to minimisation-type questions, e.g.
1. Cheapest way to connect all vertices?
- a.k.a. minimum spanning tree problem
- assumes: edges are weighted and undirected
2. Cheapest way to get from A to B?
- a.k.a shortest path problem
- assumes: edge weights positive, directed or undirected
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}