最短経路でのDijkstraアルゴリズムとFloydアルゴリズム

Dijkstraアルゴリズム
1.定義の概要
Dijkstra(ディジェストラ)アルゴリズムは、1つのノードから他のすべてのノードへの最短パスを計算するための典型的な単一ソース最短パスアルゴリズムである.主な特徴は、始点を中心に外側に層を広げ、終点まで拡張することです.Dijkstraアルゴリズムは代表的な最短パスアルゴリズムであり、データ構造、図論、オペレーティングなど、多くの専門課程で基本的な内容として詳しく紹介されています.このアルゴリズムは、図に負の重みエッジが存在しないことを要求する.
質問説明:無方向図G=(V,E)では、各エッジE[i]の長さがw[i]であると仮定し、頂点V 0から残りの各点への最短パスを見つける.(シングルソース最短パス)
 
2.アルゴリズムの説明
1)アルゴリズム思想:G=(V,E)を帯権有向図とし,図中の頂点集合Vを2つのグループに分け,第1のグループは最短経路を求めた頂点集合とする(Sで表すと,初期はSの中に1つのソース点しかなく,以降は最短経路を求めるたびに集合Sに加え,すべての頂点がSに加わるまでアルゴリズムは終了する).第2群は、最短経路が特定されていない残りの頂点の集合(Uで示す)であり、最短経路長のインクリメント順に第2群の頂点をSに順次加える.加えられる過程において、ソース点vからSまでの各頂点の最短経路長は、ソース点vからUまでの任意の頂点の最短経路長よりも大きくない.また、各頂点は1つの距離に対応しており、Sの頂点の距離はvから頂点までの最短経路長であり、Uの頂点の距離は、vからこの頂点までSの頂点のみを含む現在の最短経路長である.
2)アルゴリズムステップ:
a.初期の場合、Sはソース点、すなわちS={v}のみを含み、vの距離は0である.Uは、vを除く他の頂点、すなわち、U={残りの頂点}を含み、vがUの頂点uとエッジを有する場合、は通常の重み値であり、uがvの出辺隣接点でない場合、の重み値は∞である.
b.Uから距離vが最も小さい頂点kを選択し、kをSに加える(この選択された距離がvからkまでの最短経路長である).
c.kを新たに考慮した中間点とし、Uにおける各頂点の距離を修正する.ソース点vから頂点uまでの距離(頂点kを通る)が元の距離(頂点kを通らない)よりも短いと、頂点uの距離値が修正され、修正された距離値の頂点kの距離に上の重みが加わる.
d.すべての頂点がSに含まれるまで、ステップbおよびcを繰り返す.
コード:

//     Dijkstra  
void dijkstra(grap&g,int v){
int lowcost[M];//v     
int pre[M];//    
bool u[M];//      
int i,j,k;
int t;
int min;
for(i=0;i<g.v;i++){
    lowcost[i]=g.edge[v][i];
    u[i]=0;
    if(lowcost[i]!=0)pre[i]=v;
    else pre[i]=-1;
  }
cout<<"       ："<<endl;
lowcost[v]=0;
u[v]=1;
cout<<v<<"->";
for(i=0;i<g.v-1;i++){
min=INF;
t=v;
for(j=0;j<g.v;j++){
  if(u[j]==0&&min>lowcost[j]&&lowcost[j]!=0){t=j;min=lowcost[j];}
                }
u[t]=1;
cout<<t<<"->";
for(k=1;k<g.v;k++){
    if(u[k]==0&&(g.edge[t][k]!=0)){
  if(lowcost[k]==0)lowcost[k]=lowcost[t]+g.edge[t][k];  
  else if((lowcost[t]+g.edge[t][k])<lowcost[k]){lowcost[k]=lowcost[t]+g.edge[t][k];pre[k]=t;}
              }}
}
cout<<endl;

for(i=0;i<g.v;i++){
cout<<v<<"   "<<i<<"  :"<<lowcost[i]<<endl;}
}

Floydアルゴリズム
1.定義の概要
Floyd-Warshallアルゴリズム(Floyd-Warshall algorithm)は、任意の2点間の最短経路を解決するアルゴリズムであり、図面または負の重みを持つ最短経路問題を正しく処理し、図面への伝達閉包を計算するためにも用いられる.Floyd‐Warshallアルゴリズムの時間的複雑度はO(N 3),空間的複雑度はO(N 2)であった.
 
2.アルゴリズムの説明
1)アルゴリズムの思想原理:
Floydアルゴリズムは古典的な動的計画アルゴリズムである.通俗的な言語で記述すると,まず点iから点jへの最短経路を探すことが目標である.動的計画の観点から問題を見るには、この目標のためにもう一度解釈する必要があります(この解釈は動的計画の最も創造力に富む精華です).
任意のノードiから任意のノードjへの最短経路は2つの可能性にほかならず,1はiからjに直接,2はiからいくつかのノードkからjを通過する.そこで、Dis(i,j)がノードuからノードvまでの最短経路の距離であると仮定し、各ノードkについて、Dis(i,k)+Dis(k,j)2).アルゴリズムの説明:
a.任意の片側経路から開始する.すべての2点間の距離はエッジの重みであり、2点間にエッジが接続されていない場合、重みは無限大です.　　
b.各ペアの頂点uおよびvについて、uからwへ、およびvへの経路が既知の経路よりも短くなるように、頂点wが存在するかどうかを確認する.更新する場合.コード:

//     Floyd  
void Floyd(grap&g){
int a[M][M];//          
int path[M][M];//     
int i,j,k;
int t;
int min;
for(i=0;i<g.v;i++)
  for(j=0;j<g.v;j++){if(i==j)a[i][j]=g.edge[i][j];
                    else if(g.edge[i][j]==0)a[i][j]=INF;
		    else a[i][j]=g.edge[i][j];
                    path[i][j]=-1;}//  
for(k=0;k<g.v;k++)
{ for(i=0;i<g.v;i++)
    for(j=0;j<g.v;j++)
	if(a[i][j]>a[i][k]+a[k][j]){a[i][j]=(a[i][k]+a[k][j]);path[i][j]=k;}
 
}//  	if(a[i][j]>a[i][k]+a[k][j]){a[i][j]=(a[i][k]+a[k][j]);path[i][j]=k;}

for(i=0;i<g.v;i++){
for(j=0;j<g.v;j++)
cout<<a[i][j]<<" ";
cout<<endl;}
}