ダイクストラ法

ダイクストラ法を実装してみました。
とりあえず1時間半ぐらいで思うがままに書いてみたので、
スパゲッティです。　　

ダイクストラ法とは、グラフが与えられた時、2点間の最短距離を求めるアルゴリズムですね。

ここでは、

というグラフが与えられた場合に
sからtの間の最短経路が6になるという計算をしてます。

人間が計算するのは簡単ですが、コンピュータに計算させるには、
ひと工夫いるわけですね。

入力は、グラフを2次元配列に落としたものを使ってます。　
例えば、0→1の道は距離が2なので、
e[0][1]=2となります。

#include 

int main(){

  int v=7;
  int e[7][7]={{0,2,0,7,3,0,0},
	       {0,0,1,4,0,0,6},
	       {0,0,0,0,0,0,4},
	       {0,0,0,0,0,2,3},
	       {0,0,0,4,0,1,0},
	       {0,0,0,1,0,0,2},
	       {0,0,0,0,0,0,0}};
  int start = 0;  
  int goal = 6;

  int result;
  result = dijkstra(v, &e[0][0],start,goal);
  printf("result=%d\n",result);
  
  return 1;
}


int dijkstra(int v, int* e, int start, int goal){

  int point[v];//最短路木
  int dist_temp[v];//仮の最短距離
  int dist[v];//最短距離
  int u_flag[v];//すでに最短路木に含まれているかどうかのフラグ
  
  int i,j;

  /*** initialize ***/
  for(i=0;i dist_temp[i]) ){//近接接点のうちで、最短路木に含まれず、かつ距離が最小の点を探す。
	buf = dist_temp[i];
	buf_num=i;
      }
    }
    
    dist[buf_num]=dist_temp[buf_num];//その点を最短距離と確定
    u_flag[buf_num]=0;//最短路木に追加
    remain--;
    
    for(i=0;i

ステップ数はO(V^2)
記憶領域はO(V^2)
です。

さすがにこのデータ構造は無駄ありすぎですね＞＜
ほんで、可読性が最悪です。　　
配列使いたいけど、新たに確保しなおすのもなぁ。。。とか思いながら。。。
構造体使えばこましになりそうやけど、可変領域の確保がちょっとわからず。。

一般的にダイクストラ法はO(E*logV)で、さらに工夫によっちゃO(E+V*logV)まで落とせるみたいなので、
もうちょいと工夫してみようかと思います。