인접 리스트 표현을 위한 다익스트라 알고리즘

주어진 그래프 G(V, E)와 인접 목록 표현이 있으며 소스 정점도 제공됩니다. 그래프 G의 다른 정점에 대한 소스 정점 사이의 최소 최단 경로를 찾는 Dijkstra의 알고리즘입니다.

이 문제를 해결하기 위해 두 개의 목록을 사용합니다. 하나는 최단 경로 트리로 간주된 정점을 저장하는 것이고 다른 하나는 아직 고려되지 않은 정점을 유지하는 것입니다. 알고리즘의 각 단계에서 고려되지 않은 정점과 소스로부터 최소 거리를 갖는 정점을 찾습니다.

다른 목록은 선행 노드를 보유하는 데 사용됩니다. 선행 노드를 사용하여 소스 및 대상에서 경로를 찾을 수 있습니다.

그래프가 인접 목록을 사용하여 표현되기 때문에 Dijkstra의 최단 경로 알고리즘의 복잡성은 O(E log V)입니다. . 여기서 E는 모서리의 수이고 V는 정점의 수입니다.

입력 및 출력

입력:각 간선의 비용이 있는 그래프의 인접 목록입니다. 출력:0에서 1, 비용:3 이전:00에서 2, 비용:5 이전:10에서 3 , 비용:4 이전:10에서 4, 비용:6 이전:30에서 5, 비용:7 이전:20에서 6, 비용:7 이전:4

알고리즘

dijkstraShortestPath(g :그래프, dist, prev, 시작 :노드)

입력 - 그래프 g, 거리를 저장할 dist 목록, 선행 노드에 대한 prev 목록 및 시작 정점.

출력 - 시작에서 다른 모든 정점까지의 최단 경로입니다.

(V - 시작)의 모든 정점 u에 대해 시작 do dist[u] :=∞ prev[u] :=φ done set dist[start] =0 및 prev[start] :=φ의 모든 노드 u에 대해 V 큐 'Q'에 u를 삽입합니다. Q가 비어 있지 않은 동안 완료 do u :=큐에서 최소 요소 삭제 Q에서 u를 노드 u에 인접한 각 노드 v에 대해 집합 S에 삽입 do if dist[u]+cost(v)  
예시
 
#include#include#include#includenamespace std 사용;typedef struct nodes { int dest; int 비용;}노드;클래스 그래프 { int n; 목록<노드> *adjList; private:무효 showList(int src, list lt) { list ::iterator i; 노드 임시 노드; for(i =lt.begin(); i !=lt.end(); i++) { tempNode =*i; cout <<"(" <[n]; } 무효 addEdge(int 소스, int 목적지, int 비용) { 노드 newNode; newNode.dest =목적지; newNode.cost =비용; adjList[소스].push_back(newNode); } 무효 displayEdges() { for(int i =0; i tempList =adjList[i]; showList(i, tempList); } } 친구 void dijkstra(그래프 g, int *dist, int *prev, int start);};void dijkstra(그래프 g, int *dist, int *prev, int start) { int n =g.n; for(int u =0; u S; //빈집합 생성 S list Q; for(int u =0; u ::iterator i; i =min_element(Q.begin(), Q.end()); 정수 유 =*i; //큐의 최소 요소 Q.remove(u); S.삽입(u); //세트 목록에 u 추가 ::iterator it; for(it =g.adjList[u].begin(); it !=g.adjList[u].end();it++) { if((dist[u]+(it->비용)) dest]) { //relax (u,v) dist[it->dest] =(dist[u]+(it->cost)); 이전[그것->목적지] =u; } } }}메인() { 정수 n =7; 그래프 g(n); 정수 dist[n], 이전[n]; 정수 시작 =0; g.addEdge(0, 1, 3); g.addEdge(0, 2, 6); g.addEdge(1, 0, 3); g.addEdge(1, 2, 2); g.addEdge(1, 3, 1); g.addEdge(2, 1, 6); g.addEdge(2, 1, 2); g.addEdge(2, 3, 1); g.addEdge(2, 4, 4); g.addEdge(2, 5, 2); g.addEdge(3, 1, 1); g.addEdge(3, 2, 1); g.addEdge(3, 4, 2); g.addEdge(3, 6, 4); g.addEdge(4, 2, 4); g.addEdge(4, 3, 2); g.addEdge(4, 5, 2); g.addEdge(4, 6, 1); g.addEdge(5, 2, 2); g.addEdge(5, 4, 2); g.addEdge(5, 6, 1); g.addEdge(6, 3, 4); g.addEdge(6, 4, 1); g.addEdge(6, 5, 1); dijkstra(g, dist, prev, start); for(int i =0; i 
출력
 <이전>0 ~ 1, 비용:3 이전:00 ~ 2, 비용:5 이전:10 ~ 3, 비용:4 이전:10 ~ 4, 비용:6 이전:30 ~ 5, 비용:7 이전:20 ~ 6, 비용:7 이전:4