다익스트라의 최단경로 알고리즘을 위한 C++ 프로그램?

<시간/>

다익스트라의 알고리즘(또는 다익스트라의 최단 경로 우선 알고리즘, SPF 알고리즘) 예를 들어 도로 네트워크를 나타낼 수 있는 그래프에서 노드 사이의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 시작 정점인 소스에서 그래프의 다른 모든 지점까지의 최단 경로 트리를 생성합니다.

Dijkstra의 알고리즘은 소스에서 최소 거리를 갖는 노드 집합을 구축하여 단일 소스 노드에서 최단 경로 트리를 찾습니다.

그래프는 다음과 같습니다-

알고리즘에서 v 또는 u로 표시된 꼭짓점 또는 노드.
두 노드를 연결하는 가중 간선:(u,v)는 간선을 나타내고 w(u,v)는 가중치를 나타냅니다. 오른쪽 다이어그램에서 각 모서리의 가중치는 회색으로 표시됩니다.

알고리즘 단계

소스 정점을 제외한 모든 정점 거리 =무한대, 소스 거리 =0으로 설정
최소 우선 순위 대기열의 소스 정점을 (distance, vertex) 형식으로 푸시합니다. 최소 우선 순위 대기열의 비교는 정점 거리에 따라 이루어지기 때문입니다.
우선순위 큐에서 최소 거리로 정점을 팝합니다(처음에는 팝된 정점 =소스).
"현재 정점 거리 + 가장자리 가중치 <다음 정점 거리"인 경우 연결된 정점과 튀어나온 정점의 거리를 업데이트한 다음 새 거리를 가진 정점을 우선 순위 대기열로 푸시합니다.
팝업된 정점이 전에 방문했다면 사용하지 않고 계속 진행합니다.
우선순위 대기열이 비워질 때까지 동일한 알고리즘을 다시 적용합니다.

그래프와 그래프의 소스 정점이 주어지면 소스에서 주어진 그래프의 모든 정점까지의 최단 경로를 찾습니다. 주어진 G[][] 그래프 가중치의 행렬, n 그래프의 정점 수, u 시작 노드.

입력

G[최대][최대]={{0,1,0,3,10}, {1,0,5,0,0}, {0,5,0,2,1}, {3 ,0,2,0,6}, {10,0,1,6,0}}n=5u=0

출력

노드1의 거리=1경로=1<-0노드2의 거리=5경로=2<-3<-0노드3의 거리=3경로=3<-0노드4의 거리=6경로=4<-2<-3<-0 
 설명 
   
 인접 행렬 adj[ ][ ]에서 비용 행렬 C[ ][ ]를 만듭니다. C[i][j]는 정점 i에서 정점 j로 이동하는 비용입니다. 정점 i와 j 사이에 가장자리가 없으면 C[i][j]는 무한대입니다.
 
  
 방문 배열[ ]이 0으로 초기화됩니다.
 
 
 for(i=0;i   
 정점 0이 소스 정점이면 방문[0]은 1로 표시됩니다.
 
  
 정점 번호에서 정점의 비용을 저장하여 거리 행렬을 만듭니다. 소스 정점 0에서 0에서 n-1까지.
 
 
 for(i=1;i 
 처음에 소스 정점의 거리는 0으로 간주됩니다. 즉 distance[0]=0;
 for(i=1;i   
 거리[w]가 최소이고 방문함[w]이 0이 되도록 꼭짓점 w를 선택합니다. 방문함[w]을 1로 표시합니다.
 
  
 소스에서 나머지 정점의 최단 거리를 다시 계산합니다.
 
  
 단, 배열 방문[ ]에서 1로 표시되지 않은 정점은 거리 재계산을 위해 고려되어야 합니다. 즉, 각 정점 v
에 대해 
 
 if(방문한[v]==0) 거리[v]=min(거리[v], 거리[w]+비용[w][v])
 예시
 #include#include네임스페이스 std 사용;#define INFINITY 9999#define max 5void dijkstra(int G[max][max],int n,int startnode);int main() { 정수 G[최대][최대]={{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0 ,2,0,6},{10,0,1,6,0}}; 정수 n=5; 정수 u=0; 다익스트라(G,n,u); return 0;} 무효 dijkstra(int G[max][max],int n,int startnode) { int 비용[max][max],distance[max], pred[max]; int 방문[max],count,mindistance,nextnode,i,j; for(i=0;i