● モジュール#2 pathSearch （最短経路探索）のC言語ソースコード

 void pathSearch(  int        nNode         //  ノードの数
		,int        startPoint    //  出発ノードの番号 
		,int        endPoint      //  到着ノードの番号
		,Node_type  Node[ ]       //  ノードの接続情報テーブル
		,Link_type  Link[ ]       //  リンクの情報（接続先ノード，距離）テーブル
		,float&     minDist       //  出発ノードから到着ノードまでの最短距離 
		,int  &     nRoute        //  出発ノードから到着ノードまでの経由ノード数 
		,int        routeNode[ ]  //  出発ノードから到着ノードまでのルートノード
                ）
{
#define NIL      0
#define UNCHECK  0
#define CHECKED  1
#define INFINITE  999.99
int    p, i, i1, i2 ,node_q;
float  minValue ,dist_q;
int    check_tbl[MAX_NODE+1]   // 通過フラッグが立っているか否かを示すチェック表
      ,route    [MAX_NODE+1];  // 経由した1つ前のノード番号を格納しておく表
float  totalDist[MAX_NODE+1];  // ノードまでの経由距離合計を格納しておく表
//---- 初期値の設定 -----
for (i=1; i <= nNode; i++)
{   
     totalDist [i] = INFINITE;
     check_tbl [i] = UNCHECK;
};

totalDist[startPoint] = 0.0;
route    [startPoint] = NIL;
p  = startPoint;  //-----  開始ノードの設定 -----以後 pは着目しているノードを示す

   while( p != endPoint)   
{  
   /* 【 ノードに到着した各トークンの経過時間比較 】 */
      check_tbl[p] = CHECKED;          // トークンを出発させるノードに通過フラッグを立てる
      i1 = Node[p].link_position;      // Link表におけるノードpのデータの格納開始位置
      i2 = i1 + Node[p].link_size - 1; // Link表におけるノードpのデータの終り位置
    
        for (i = i1; i <= i2; i++)  //  p にリンクされているすべてのノードをチェック
        {
           node_q  = Link[i].connect_node;   // p のリンク先の1つをnode_qとする
           if (check_tbl[node_q] == UNCHECK) // 通過フラッグが立っていないノード？
           {
	        dist_q = Link[i].dist;
                 if(totalDist[p] + dist_q < totalDist[node_q]) 
                 {    
                   /* 【 ｐを経由したルートの方が，経由距離合計が短いので 
                           ｐ経由に変更する 】  */
		    totalDist[node_q] = totalDist[p] + dist_q;
		    check_tbl[node_q] = UNCHECK;
		    route[node_q]     = p;           // node_q は p を経由する
	         }
	  　}
        }
   	/*  【 次にトークンを進めるべきノードの決定 】
             -----  ネットワークのチェックされていないノードの中からそれまでの経路長が
                    最も短いノード p を選び出す．選び出されたｐは、次の探索操作で
                    着目するノードになる                                        ---- */

【 課題１】として埋めるべき部分
        ＜ヒント＞ 経由合計距離は配列totalDist に格納されている

   } 
    minDist = totalDist[endPoint];
}