Suppose each proposed rail link between two cities has a distance in miles. An unweighted graph says which cities connect; a weighted graph also records the distance of each connection. Those values make it possible to ask which links minimize a network’s total length or which route is shortest from a starting city. section 4.1 section 4.3 section 4.4
In Swift, `WeightedEdge<W>` stores endpoint indices `u` and `v` plus a `weight`. `WeightedGraph<V, W>` keeps vertices and adjacency lists of those edges. Its weighted-neighbor method returns `(vertex, weight)` pairs. The graph’s edge insertion is bidirectional: it also stores a reversed edge, preserving the weight. section 4.3 section 4.1
open class WeightedEdge<W: Comparable & Summable>: Edge, Comparable {
public var u: Int
public var v: Int
public let weight: W
public var reversed: Edge {
return WeightedEdge(u: v, v: u, weight: weight)
}
public init(u: Int, v: Int, weight: W) {
self.weight = weight
self.u = u
self.v = v
}
//Implement CustomStringConvertible protocol
public var description: String {
return "\(u) <\(weight)> \(v)"
}
//MARK: Operator Overloads for Comparable
static public func == <W>(lhs: WeightedEdge<W>,
rhs: WeightedEdge<W>) -> Bool {
return lhs.u == rhs.u && lhs.v == rhs.v && lhs.weight == rhs.weight
}
static public func < <W>(lhs: WeightedEdge<W>, rhs:
WeightedEdge<W>) -> Bool {
return lhs.weight < rhs.weight
}
}
Inspect how the edge retains its weight when reversed and compares edges by weight for selecting low-cost links. section 4.3
Weights are generic, but the algorithms need to compare and add them. `Comparable` supplies comparisons; the custom `Summable` protocol requires `+`. The implementation adds `Summable` conformance to `Int`, `Double`, and `Float`. An empty collection of weighted edges has no first weight to start a total, so `totalWeight` returns an optional result. section 4.3
A city network
A `WeightedGraph<String, Int>` can contain Seattle, San Francisco, and their other proposed connections. Adding Seattle–San Francisco with weight `678` records a 678-mile link; a weighted-neighbor listing shows San Francisco alongside `678`. The same larger network supports a minimum spanning tree with total weight `5372` and a shortest route from Los Angeles to Boston with total weight `2605`. section 4.3 section 4.4
Two questions use the weights differently:
- A minimum spanning tree selects low-weight edges that connect the vertices without cycles. The priority-queue implementation assumes undirected edges; if the graph is disconnected, it spans only the starting vertex’s component. section 4.3
- A single-source shortest-path search finds the lowest total edge weight from one vertex to each other vertex. Dijkstra’s algorithm records distances and the edge used to reach each vertex, updating them when it finds a shorter route. section 4.4
