ダイクストラの最短経路アルゴリズム用のC++プログラム？

ダイクストラのアルゴリズム（またはダイクストラの最短経路優先アルゴリズム、SPFアルゴリズム） は、グラフ内のノード間の最短経路を見つけるためのアルゴリズムであり、たとえば、道路ネットワークを表す場合があります。アルゴリズムは、開始頂点であるソースからグラフ内の他のすべてのポイントまでの最短パスのツリーを作成します。

ダイクストラのアルゴリズムは、ソースからの距離が最小のノードのセットを構築することにより、単一のソースノードから最短パスツリーを見つけます。

グラフには次のものがあります-

• アルゴリズムでvまたはuで示される頂点またはノード。

• 2つのノードを接続する重み付きエッジ：（u、v）はエッジを示し、w（u、v）はその重みを示します。右の図では、各エッジの重みが灰色で書かれています。

アルゴリズムの手順

• ソース頂点を除くすべての頂点の距離=無限大に設定し、ソース距離=0に設定します。
• 最小優先度キューでの比較は頂点の距離に応じて行われるため、ソース頂点を最小優先度キューの形式（距離、頂点）でプッシュします。
• 優先度付きキューからの距離が最小の頂点をポップします（最初はポップされた頂点=ソース）。
• 「現在の頂点の距離+エッジの重み<次の頂点の距離」の場合は、接続された頂点の距離をポップされた頂点まで更新してから、新しい距離の頂点を優先キューにプッシュします。
• ポップされた頂点が以前にアクセスされた場合は、それを使用せずに続行します。
• 優先度付きキューが空になるまで、同じアルゴリズムを再度適用します。

グラフとグラフ内のソース頂点が与えられた場合、ソースから与えられたグラフ内のすべての頂点への最短経路を見つけます。グラフの重みのG[][]行列が与えられた場合、nはグラフの頂点ではなく、uは開始ノードです。

入力

G[max][max]={{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

出力

Distance of node1=1
Path=1<-0
Distance of node2=5
Path=2<-3<-0
Distance of node3=3
Path=3<-0
Distance of node4=6
Path=4<-2<-3<-0

説明

• 隣接行列adj[][]からコスト行列C[][]を作成します。 C [i] [j]は、頂点iから頂点jに移動するためのコストです。頂点iとjの間にエッジがない場合、C[i][j]は無限大です。

• 配列visited[]はゼロに初期化されます。

for(i=0;i<n;i++)
   visited[i]=0;

• 頂点0がソース頂点である場合、visited[0]は1としてマークされます。

• 頂点番号からの頂点のコストを格納することにより、距離行列を作成します。ソース頂点0から0からn-1。

for(i=1;i<n;i++)
distance[i]=cost[0][i];

最初は、ソース頂点の距離は0と見なされます。つまり、distance [0] =0;

for(i=1;i<n;i++)
visited[i]=0;

• 頂点wを選択し、distance [w]が最小で、visited[w]が0になるようにします。visited[w]を1としてマークします。

• ソースから残りの頂点の最短距離を再計算します。

• 距離の再計算では、visited[]の配列で1としてマークされていない頂点のみを考慮する必要があります。つまり、各頂点v

if(visited[v]==0)
   distance[v]=min(distance[v],
   distance[w]+cost[w][v])

例

#include<iostream>
#include<stdio.h>
using namespace std;
#define INFINITY 9999
#define max 5
void dijkstra(int G[max][max],int n,int startnode);
int main() {
   int G[max][max]={{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}};
   int n=5;
   int u=0;
   dijkstra(G,n,u);
   return 0;
}
void dijkstra(int G[max][max],int n,int startnode) {
   int cost[max][max],distance[max],pred[max];
   int visited[max],count,mindistance,nextnode,i,j;
   for(i=0;i<n;i++)
      for(j=0;j<n;j++)
   if(G[i][j]==0)
      cost[i][j]=INFINITY;
   else
      cost[i][j]=G[i][j];
   for(i=0;i<n;i++) {
      distance[i]=cost[startnode][i];
      pred[i]=startnode;
      visited[i]=0;
   }
   distance[startnode]=0;
   visited[startnode]=1;
   count=1;
   while(count<n-1) {
      mindistance=INFINITY;
      for(i=0;i<n;i++)
         if(distance[i]<mindistance&&!visited[i]) {
         mindistance=distance[i];
         nextnode=i;
      }
      visited[nextnode]=1;
      for(i=0;i<n;i++)
         if(!visited[i])
      if(mindistance+cost[nextnode][i]<distance[i]) {
         distance[i]=mindistance+cost[nextnode][i];
         pred[i]=nextnode;
      }
      count++;
   }
   for(i=0;i<n;i++)
   if(i!=startnode) {
      cout<<"\nDistance of node"<<i<<"="<<distance[i];
      cout<<"\nPath="<<i;
      j=i;
      do {
         j=pred[j];
         cout<<"<-"<<j;
      }while(j!=startnode);
   }
}