最短経路問題

1. 最短経路問題
   A君：「急いで＊＊町に行きたいんだけど、どの道が一番速いのかな？」
   B君：「カーナビで調べてみなよ。」
   A君：「でもカーナビはどのように調べているんだい」
   
   
2. グラフと最短経路問題
   　
   1. グラフ構造
      町とその間の道はグラフ構造で表現できます。グラフでは、場所を「節点」、道を「枝」と呼びます。グラフは節点を丸で、枝をその間の直線で、図示することができます。道を通過する時間は枝の「重み」として呼びます。重みは枝のラベルとして表示できます。直接枝で接続されていない、二つの節点間を結ぶ枝のつながりを「経路」と呼びます。経路上の各枝の重みの合計を経路の「重み」と呼びます。
      
      
   2. 最短経路問題
      二つの節点を結ぶ最小重みの経路を、最短経路と呼びます。ここでの問題は、グラフの最短経路を求めることです。グラフは仕事とその所要時間、部品とその間隔、など多くの問題を表現できます。最短経路問題は、最小の所要時間や必要な最小のスペース等を求める一般的なアルゴリズムとなります。
      
      
   3. 経路の数え上げ
      　最短経路を求めるにはすべての経路を求めて、その重みの最小値を求める方法が考えられます。しかし、一般に経路の数は非常に多い、経路にループが含まれる場合ループを切断するなどの処理が必要、等の問題があります。そこで、最短経路を求めるには、他の方法がよく利用されます。
      
      
   4. ラベリング法
      　最短経路問題の解法には、ラベリング法がよく利用されます。ラベリング法では、各節点にラベル（数値）を用意します。最初、開始節点のラベルを0としその他の節点のラベルは無限大（∞）とします。このラベルの値を、開始点からの最短距離になるよう順次更新します。接点 j に接続する接点を　i1, i2, ..ik　とします。また、接点 j のラベルの値を　val(j) とします。このとき、
      　val(ik) + b(ik,j) の値が　val(j) より小さければ、val(j)　の値を val(ik) + b(ik,j) で置き換えます。val(ik) + b(ik,j)　は、開始接点から ik までの最短距離に「ik から接点j までの枝の重み」を加えた値ですから、接点 j　までの経路の一つです。この値が　現在の接点 j のラベルより小さいとき、ラベルをこの値に置き換えます。
      　ラベル j の値が置き換わると、ラベル　ｊ が接続する接点のラベルを置き換える可能性があります。したがって、どの接点のラベルも変化しなくなるまで、ラベルの更新を続ける必要があります。
      
      
      1. 例
         下はラベリング法で、最短経路を求めた例です。最初、開始点のラベルを0とします。他の接点のラベルは無限大（∞）相当の1000とします。
         
         
         
         　この状態で、始点以外のラベルの接点を更新します。上の接点は 0+10 で10、下の接点のラベルは15になります。右の終点のラベルは、10からの経路では22、15からの経路では21になりますから、短い方の21になります。
         
         
         
         ラベルの値が変化しましたから、再度、ラベルの値を計算し直す必要があります。この場合、各接点の値は既に最小値になっていますから、もう変化しません。
         
         
   5. 実験
      　下のアプレットで実験をして下さい。「新接点ボタン」を押してから、画面でクリックすると、接点が登録されます。右下に数値を設定し、接点の内部でクリックし、目的の接点までドラッグすると設定した数値を重みとする枝が生成されます。枝の重みは、再度、節点の間をドラッグすることで変更できます。
      　最短経路を求めるには、まず、始点ボタンを押してから、始点とする接点をクリックします。これで、始点のラベルは０、他の接点のラベルは1000（∞）となります。
      　「開始」ボタンを押すと、最短経路が計算されます。1回各接点のラベルを更新します。どこかの接点でラベルの値が更新されると、「開始」ボタンは「ステップ」ボタンになり、「ステップ」ボタンを押すと1回ラベルの値の更新作業を行います。どの接点のラベルも更新されないと（最短経路が計算された場合）、「ステップ」ボタンは「開始」ボタンに変わります。
      
      
      
      
3. プロジェクトの作成
   
   
   1. Applet1クラス：グラフの生成処理
      
      1. データ構造
         接点をNodeクラス、枝をArcクラスで表現します。グラフは、NodeとArcのリスト（ベクタ）で表現します。
         
         　Vector Nodes=new Vector();
         　Vector Arcs=new Vector();
         

         class Node{
           Point loc;
           int val;
         
           Node(Point p){
             loc=new Point();
             loc.x=p.x;
             loc.y=p.y;
             val=1000;
           }
         }

         class Arc{
           int srcId=-1;
           int tgtId;
           int weight;
         
           Arc(int sid,int tid,int wt){
             srcId=sid;
             tgtId=tid;
             weight=wt;
           }
         }

         
         
      2. 接点の生成：mouseclicked()
         「新接点」ボタンを押されたら、newNodeをtrueにします。画面でクリックされると、他の挿入済みの節点とはなれていれば、そこに新規接点を生成します。
         　以下は、マウス位置(p)が、登録済み接点(nd)の近くにある場合、処理を終了します。
         

               for(int i=0;i<Nodes.size();i++){
                 Node nd=(Node)Nodes.elementAt(i);
                 if(match(p,nd.loc)){
                   return;
                 }
               }

         以下は、接点を追加し、再表示を行います。

               Node nd=new Node(p);
               Nodes.add(nd);
               newNode=false;
         　　　repaint();

         mouseclicked()は、マウスボタンがクリックされたのち、話されたとき呼び出されます。したがって、mousePressedやmouseReleasedで代用できますが、ここでは処理を分散させるため利用しています。どちらの関数も呼び出されるので、重複処理をしないよう注意する必要があります。
         
         
      3. 枝の登録：mousePressed、mouseDragged、mouseReleased
         　枝の登録は、3種のマウスボタンイベントを利用します。ボタンを押したとき、マウス位置が節点の上で、「新節点」や「始点」ボタンが有効でなければ、ドラッグ（枝の生成）を開始します。このとき、dragOk=trueにしてドラッグ中であることを指示し、最初の節点番号を　srcId　に記録します。
         　mouseDragged(MouseEvent e)では、dragptにマウスの座標を設定し、再表示します。これて、ドラッグ中の枝が表示されます。
         　mouseReleased(MouseEvent e)は、ボタンが放されたときの処理をします。マウスが登録された節点の上にあれば、その節点番号を　tgtId　とし、枝を追加します。このとき、枝の重みをwtに読みとっています。checkDouble()は、二つの節点が同じかどうか調べています。
         　

           public void mouseReleased(MouseEvent e){
             Point p=e.getPoint();
             if(dragOk){
               for(int i=0;i<Nodes.size();i++){
                 Node nd=(Node)Nodes.elementAt(i);
                 if(match(p,nd.loc) && srcId >=0 ){
                   if(i != srcId  ) tgtId=i;
                   int wt=Integer.parseInt(textField1.getText());
                   Arc arc=new Arc(srcId,tgtId,wt);
                   checkDouble(srcId,tgtId);
                   if (tgtId >=0) Arcs.add(arc);
                 }
               }
             }
             dragOk=false;
             srcId=-1;tgtId=-1;
             repaint();
           }

         
         
      4. グラフの描画
         　以下はベクタNodesの接点を表示します。 EnumerationはNodesのリストemを返します。em.hasMoreElements()で、emに残りの要素があることの確認、em.nextElement()で次の要素を取り出します。
         
         

             Enumeration em=Nodes.elements();
             while(em.hasMoreElements()){
               Node nd=(Node)em.nextElement();
               pt=nd.loc;
               g.setColor(clb);
               g.fillOval(pt.x-20,pt.y-10,40,20);
               g.setColor(clw);
               g.drawString(Integer.toString(nd.val),pt.x-15,pt.y+5);
               g.setColor(clb);
             }

         
         以下は、Arcsに記録された方向付の枝とその重みを表示します。枝の中間に重みを表示するため、重みを表示する矩形を黒で塗りつぶし、その上から白色で重みの数値を表示します。

             Enumeration ema=Arcs.elements();
             Point pc=new Point();
             while(ema.hasMoreElements()){
               //draw line
               Arc ac=(Arc)ema.nextElement();
               Node ns=(Node)(Nodes.elementAt(ac.srcId));
               Node nt=(Node)(Nodes.elementAt(ac.tgtId));
               Point psrc=ns.loc;
               Point ptgt=nt.loc;
               g.setColor(clb);
               g.drawLine(psrc.x,psrc.y,ptgt.x,ptgt.y);
         
               //draw arc
               //矢印を表示します。
         
               //draw weight
               pc.x=(psrc.x+ptgt.x)/2;
               pc.y=(psrc.y+ptgt.y)/2;
               g.setColor(clb);
               g.fillRect(pc.x-10,pc.y-7,20,15);
               g.setColor(clw);
               g.drawString(Integer.toString(ac.weight),pc.x-7,pc.y+5);
               g.setColor(clb);
             }

         
         
   2. procクラス：ラベルの計算
      
      1. ラベルの値の更新
         　最短経路を求める、中核の部分です。changedはどれかの節点のラベルが変化したときtrueにします。apltは、ArcsやNodesへの参照子です。（aplt.Arcsで枝のベクタを参照していますが、オブジェクト指向型のプログラムになっていません）。各枝について、
         　if(nt.val > ns.val + ac.weight)
         で、ラベルの値が小さくなるか判定し、真の場合、ラベルを更新して、changedをtrueにします。
         

             boolean changed=true;
             while(changed){
               changed=false;
               Enumeration ema=aplt.Arcs.elements();
               //System.out.println("labelling");
               while(ema.hasMoreElements()){
                 Arc ac=(Arc)ema.nextElement();
                 Node ns=(Node)(aplt.Nodes.elementAt(ac.srcId));
                 Node nt=(Node)(aplt.Nodes.elementAt(ac.tgtId));
                 if(nt.val > ns.val + ac.weight) {
                   nt.val = ns.val + ac.weight;
                   changed=true;
                 }
               }
               aplt.repaint();
             }

         
         
      2. スレッドと同期
         procクラスはThreadを継承しています。これは、ステップボタンで、ラベル処理をステップ実行するためです。ラベルの値を１回更新すると、
         　waitButton();
         で、ステップボタンが押されるまで、このスレッドは　wait　状態に入ります。
         

            synchronized  public void waitButton(){
              try{
                wait();
                }catch( InterruptedException e){}
            }

         ステップボタンが押されると、step()　処理を行い、notify();でwait状態を解除します。同期処理を行うため、各メソッドには、synchronized　の指定が必要です。
         

            synchronized public void step(){
              notify();
            }