Bellman Ford in an acyclic weighed undirected graph

BellmanFord.swift

struct Edge {
    var u: Int
    var v: Int
    var weight: Int
    
    func other(_ vertex: Int) -> Int {
        return vertex == u ? v : u
    }
}

class Graph {
    private(set) var adj: [[Edge]]
    let V: Int
    
    init(_ V: Int) {
        adj = Array(repeating: [], count: V)
        self.V = V
    }
    
    func addEdge(_ e: Edge) {
        adj[e.u].append(e)
        adj[e.v].append(e)
    }
}

// O(V*E)
func bellmanFord(_ graph: Graph, _ s: Int) -> [Int] {
    let inf = 0x3f3f3f3f
    var distTo = Array(repeating: inf, count: graph.V)

    var q = [s]
    distTo[s] = 0

    func relax(_ v: Int) {
        for e in graph.adj[v] {
            let w = e.other(v)
            if distTo[w] > distTo[v] + e.weight {
                distTo[w] = distTo[v] + e.weight
                q.append(w)
            }
        }
    }

    while !q.isEmpty {
        let v = q.removeFirst()
        relax(v)
    }

    return distTo
}