최단경로 개념

최단 경로

최단 경로 속성

• 최단경로의 부분경로 역시 최단경로다.
  출발정점으로부터 다른 모든 정점에 이르는 최단경로들의 트리가 존재한다. 이를 단일점 최단경로라고 부른다.

  음의 무게를 가지는 간선과 싸이클

  가중 방향, 무방향 그래프에 음의 무게를 가진 싸이클이 존재한다면 최단경로는 존재하지 않는다.

그래프	알고리즘	시간
음의 무게를 가진 간선이 없는 그래프	Dijstra	$O(mlogn) or O(n^2)$
음의 무게를 가진 간선이 있는 방향 그래프	bellman-Ford	$O(mn)
비가중그래프	BFS	$O(m+n)$
DAG	위상순서	$O(m+n)$
## 최단경로 알고리즘
### Dijkstra

Alg DijkstraShortestPaths(G,s)

1. for each v to G.vertices()
    d(v) = INF
2. d(s) = 0
3. Q = a priority queue contaning all the vertices of G using d labels as keys
4. while(!Q.isEmpty()){
    u = Q.removeMin()
    for each e to G.incidentEdges(u){
        z = G.opposite(u,e)
        if(z in Q.elements()){
            if(d(u)+ w(u,z)<d(z)){
                d(Z) = d(u) + w(u,z)
                Q.replaceKey(z,d(z))
            }
        }
    }
}

1. 여기서도 거리 다 무한으로 놓고 하나 뽑아서 0으로 두며, Q에 정점 전부 넣는다.
2. Q가 빌때까지 Q에서 가장 작은 값을 꺼내서 모든 인접 정점을 Q에 있는지 확인 후 거리를 계산하고, 거리가 짧으면 거리를 업데이트 후에 Q를 재정렬한다.(간선완화)