최단경로 알고리즘 관련 문제

 

1.모든 간선의 무게가 동일한 방향그래프 G에서
주어진 두 정점 사이의 최단 경로를 찾는 가장
효율적인 알고리즘은 무엇이며, 수행 시간은?

 

 

2. Dijkstra 알고리즘 확장.

Dijkstra 알고리즘을, s로부터 G의 다른 모든 정점
v에 이르는 거리가 아닌, G의 특정 정점 t에 이르는
최단 거리만을 출력하도록 수정하라.

 

* DijkstraShortestPathsSingleTarget(G, s, t): As an extension
to the Dijkstra’s algorithm, computes the shortest paths
from vertex s to vertex t