DijkstraShortestPath.swift

internal func shortestPath(source: Vertex, destination: Vertex) -> Path? {
    var frontier: [Path] = [] {
        didSet {
            frontier.sortInPlace()
        }
    }
    
    var finalPaths: [Path] = [] {
        didSet {
            finalPaths.sortInPlace()
        }
    }
  
    // the frontier is made by a path that starts nowhere and ends in the source
    frontier.append(Path(toVertex: source))
  
    while !frontier.isEmpty {
        let cheapestPathInFrontier = frontier.removeFirst()
    
        guard !cheapestPathInFrontier.endVertex.visited else { continue }

        cheapestPathInFrontier.endVertex.visited = true
    
        if (cheapestPathInFrontier.endVertex === destination) {
            finalPaths.append(cheapestPathInFrontier)
            continue
        }
    
        for edge in cheapestPathInFrontier.endVertex.edges where !edge.to.visited {
            let newPath = Path(toVertex: edge.to, viaEdge: edge, viaPath: cheapestPathInFrontier)
      
            frontier.append(newPath)
        }
    }
    return finalPaths.first
}