A shortest-path algoritnm

Dijkstra's Algorithm

Input:    A connected, weighted graph in which all weights are positive;

vertices a and z

Output:    L(z), the length of a shortest path from a to z

dijkstra(w, a, z, L){
    L(a) = 0
    for all vertices x≠a
        L(x) = ∞
    T = set of all vertices
 
    while(z∈T){
        choose v∈T with minimum L(v)
        T = T-{v}
        for each x∈T adjacent to v
            L(x) = min{L(x), L(v) + w(v, x)}
    }
}

2~5행:     vertex a의 길이를 0으로 설정하고 a를 제외한 나머지 vertex의 L은 ∞로 설정한다. T는 그래프              의 모든 vertex의 집합이다.

8~11행:     T안에있는 vertex 중에서 L이 최소인 vertex v를 선택하고 그 v를 집합 T에서 삭제한다. T에                 포함되어 있는 것중 v와 연결되어 있는 vertex에 대하여, L를 업데이트한다. 이것은 z가 T에                 포함되지 않을 때가지 반복한다.

 ***최소 path 찾기*** vertex에 label을 붙일 때, 최소 길이 뿐만아니라 이어지는 바로 전 vertex의 이름을 같이 적으면 두 vertex 사이의 최소 path를 찾을 수 있다.