if (A.pathLengthFromStart + AB.weight) < B.pathLengthFromStart {
    B.pathLengthFromStart = A.pathLengthFromStart + AB.weight
    B.pathVerticesFromStart = A.pathVerticesFromStart
    B.pathVerticesFromStart.append(B)
}

open class Vertex {

    // 모든 정점은 고유해야 하므로 식별자를 설정한다.
    open var identifier: String

    // 다익스트라 알고리즘에서 모든 정점은 최소한 하나의 다른 정점과 연결되어야 한다. 하지만 초기에는 이웃이 없는 상태로 정점을 생성하고, 이후에 이웃을 설정하는 경우도 있다. 따라서 초기값으로 이웃 배열은 비어 있다.
    // 배열은 (Vertex, Double) 튜플을 포함한다. Vertex는 이웃 정점이고, Double은 그 이웃까지의 간선 가중치이다.
    open var neighbours: [(Vertex, Double)] = []

    // 알고리즘 설명에서 언급했듯이, 시작점에서 모든 정점까지의 기본 경로 길이는 가능한 한 크게 설정한다.
    // 이 값은 알고리즘 실행 중에 업데이트되므로 var로 선언한다.
    open var pathLengthFromStart = Double.infinity

    // 이 배열은 시작 정점에서 이 정점까지 도달하기 위해 거쳐야 하는 정점들을 포함한다.
    // 시작점에서의 경로 길이와 마찬가지로, 이 배열도 알고리즘 실행 중에 변경된다.
    open var pathVerticesFromStart: [Vertex] = []

    public init(identifier: String) {
        self.identifier = identifier
    }

    // 이 함수는 동일한 정점 배열을 다시 사용하여 다른 시작 정점으로 경로를 계산할 수 있게 한다.
    // 새로운 시작 정점을 설정하고 경로를 다시 계산할 때, 그래프 정점의 캐시를 지운다.
    open func clearCache() {
        pathLengthFromStart = Double.infinity
        pathVerticesFromStart = []
    }
}

extension Vertex: Hashable {
    open var hashValue: Int {
        return identifier.hashValue
    }
}

extension Vertex: Equatable {
    public static func ==(lhs: Vertex, rhs: Vertex) -> Bool {
        return lhs.hashValue == rhs.hashValue
    }
}

public class Dijkstra {
    // 그래프의 모든 정점을 저장하는 변수이다.
    // 정점이 고유하다고 가정하므로, 배열 대신 Set을 사용한다. 이 접근 방식은 나중에 몇 가지 이점을 제공한다.
    private var totalVertices: Set<Vertex>

    public init(vertices: Set<Vertex>) {
        totalVertices = vertices
    }

    // Vertex 클래스 구현에서 clearCache 함수를 기억하는가?
    // 이 함수는 모든 저장된 정점의 캐시를 지우는 래퍼이다.
    private func clearCache() {
        totalVertices.forEach { $0.clearCache() }
    }

    public func findShortestPaths(from startVertex: Vertex) {
	// 시작 정점에서 최단 경로를 찾기 전에, 그래프가 깨끗한 상태인지 확인하기 위해 정점 캐시를 지운다.
	// Vertex는 클래스이고, 클래스는 참조로 전달된다는 점을 기억하라. 따라서 이 클래스 외부에서 정점을 변경하면, totalVertices Set 내부의 정점에도 영향을 미친다.
        clearCache()
	// 이제 모든 정점은 Double.infinity의 pathLengthFromStart와 빈 pathVerticesFromStart 배열을 갖는다.

	// 알고리즘의 다음 단계는 시작 정점의 pathLengthFromStart와 pathVerticesFromStart를 설정하는 것이다.
        startVertex.pathLengthFromStart = 0
        startVertex.pathVerticesFromStart.append(startVertex)

	// 여기서 주요 부분이 시작된다. while 루프를 사용해 그래프의 모든 정점을 순회한다.
	// 이를 위해 currentVertex 변수를 정의하고, 각 while 주기 끝에 이 변수를 변경한다.
        var currentVertex: Vertex? = startVertex

        while let vertex = currentVertex {

    	    // 다음 코드는 정점을 방문한 것으로 표시하는 구현이다.
    	    // 이미 말했듯이, 그래프에서 방문하지 않은 정점만 확인해야 한다.
	    // 따라서 Set에서 정점을 삭제하면, *"if !vertex.visited then"* 같은 확인을 건너뛸 수 있다.
            totalVertices.remove(vertex)

	    // filteredNeighbours는 아직 방문하지 않은 현재 정점의 이웃을 포함하는 배열이다.
            let filteredNeighbours = vertex.neighbours.filter { totalVertices.contains($0.0) }

	    // 이 이웃들을 순회한다.
            for neighbour in filteredNeighbours {
		// neighbour.0 또는 neighbour.1보다 더 명확한 변수명을 사용한다.
                let neighbourVertex = neighbour.0
                let weight = neighbour.1

		// 이웃에게 제공할 수 있는 새로운 가중치를 계산한다.
                let theoreticNewWeight = vertex.pathLengthFromStart + weight

		// 이 값이 이웃의 현재 pathLengthFromStart보다 작다면, 다음 코드를 실행한다.
                if theoreticNewWeight < neighbourVertex.pathLengthFromStart {

		    // 새로운 pathLengthFromStart를 설정한다.
                    neighbourVertex.pathLengthFromStart = theoreticNewWeight

		    // 새로운 pathVerticesFromStart를 설정한다.
                    neighbourVertex.pathVerticesFromStart = vertex.pathVerticesFromStart

		    // 현재 정점을 이웃의 pathVerticesFromStart에 추가한다.
                    neighbourVertex.pathVerticesFromStart.append(neighbourVertex)
                }
            }

	    // totalVertices가 비어 있다면, 즉 모든 정점을 방문했다면 루프를 종료한다.
            if totalVertices.isEmpty {
                currentVertex = nil
                break
            }

	    // 루프가 종료되지 않았다면, 방문하지 않은 정점 중 다음으로 확인할 정점을 선택한다.
	    // 다음 정점의 pathLengthFromStart는 가장 작은 값이어야 한다.
            currentVertex = totalVertices.min { $0.pathLengthFromStart < $1.pathLengthFromStart }
        }
    }
}