predecessor subgraph 는 정의에서 알 수 있듯이 V에 속한 v중 predecessor가 존재하는 모든 v가 집합에 속하게 되며 edge는 v와 v.pi를 이어주어 s로부터 vertex들의 경로를 알게 해준다.
A. v를 힙 내에서 찾는 것보다는 v.d를 업데이트한 v를 힙에 하나 더 넣고 visited배열을 만들어 힙에서 뺄 때 visited여부를 확인하는 것이 나을 것이다.
[정리]
0. 소스를 제외한 모든 노드 distance INF로 초기화, s.d = 0, s 방문
-
현재 방문한 노드와 연결된 노드 들의 distance 갱신
-
현재 방문 가능한 노드 들중 가장 distance가 짧은 노드 방문
(지금까지 최단거리였고 최단거리 + 최단거리는 최단거리 이므로 현재 distance가장 짧은건 더 이상 건드릴 필요 X, 어차피 전부 현재 거리들에서 갱신될 것이므로!)
(현재 방문한 노드에서 방문 가능한 노드들의 distance를 적어 우선순위 큐에 넣으면 된다)
- 우선순위 큐가 빌 때까지 1 ~ 2 반복
Topological Sort -> 순서는 DFS끝나는 순서대로, 그래프의 adjacency matrix(or List)는 그대로!
위상정렬은 가야하는 순서
즉, 앞에서부터 가면 뒤에서 앞으로는 못 가므로 앞에서 뒤의 최단거리를 구하면 그게 최단거리! 즉, 귀납적으로 최단거리를 구할 수 있다.
