最小生成ツリーと最短パスの違いと実現方法

最小生成ツリーを区別すると、トポロジー全体のすべてのパスの和が最小になるが、任意の2点間が最短パスであることは保証されない.最短経路は一点から目的地までの経路が最小です.二実現方法1.最小生成ツリー最小生成ツリーには、PrimsアルゴリズムとKruskalアルゴリズムの2つのアルゴリズムがあります.Kruskalアルゴリズム:エッジの重み付け値をインクリメントすることにより,重み付け値が最も低いエッジを一度に探し出して最小生成ツリーを構築し,追加するたびに生成ツリーにループができず,N−1エッジが見つかるまで知ることを規定する.Primsアルゴリズム:N−1エッジが見つかるまで、臨界エッジを1つ加えるたびに最小生成ツリーを確立する.このルールは、開始時に生成する木の集合(集合U)を始点とし、生成木の集合に隣接する辺(集合V)のうち、重み値が最も小さい辺を探し出して生成木を作成し、新たに加えられた辺がループを起こさないことを判断するために、新たに加えられた辺ごとに、生成木の集合に頂点が1つだけ許され、このステップを繰り返し実行することである.N−1辺が見つかるまで.次に、Primsアルゴリズムを実装するコードを示します.

            while(alreadyVisited.size() != Switches.size())
            {
                Vector neighbors = getNeighborSet(topo, Switches, alreadyVisited);
                Vector CostOfNeighbors = new Vector();
                int cost = 40000000;
                ASwitch srcsw = null, dstsw = null;
                for(int i = 0;i < neighbors.size();i++)
                {
                    ASwitch sw1 = (ASwitch)neighbors.get(i);
                    for(int j = 0;j < alreadyVisited.size();j++)
                    {
                        ASwitch sw2 = (ASwitch)alreadyVisited.get(j);
                        int tempcost = getCost(topo, sw1, sw2, insid, "legacy");
                        if( (tempcost > 0) && (tempcost < cost ))
                        {
                            cost = tempcost;
                            srcsw = sw1;
                            dstsw = sw2;
                        }
                    }
                }//end for neighbors
                //           
                alreadyVisited.add(srcsw);
                
                treenode temptr = new treenode();
                temptr.Mac = srcsw.SWName;
                current.childlist.push(temptr);
                current = temptr;
            }//end while

2最短パス
アルゴリズム記述(ここではノード1から各点までのdijkstraアルゴリズムを記述し、Wa->bはa->bのエッジの重み値を表し、d(i)は最短パス値である)
1.セットS={2,3,...n},配列d(1)=0,d(i)=W 1->i(1,i間にエッジが存在する)or+無限大(1.i間にエッジが存在しない)
2.Sでは、d(j)=min{d(i)、iをS}とし、S=S-{j}とし、Sが空セットであればアルゴリズムを終了し、そうでなければ3
3.すべてのiに対してSに属し、エッジj->iが存在する場合、d(i)=min{d(i)、d(j)+Wj->i}を置き、2回転する
Dijkstraアルゴリズムは,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の頂点のみを含む現在の最短経路長である.
アルゴリズムの具体的な手順
(1)初期の場合,Sはソース点,すなわちS=のみを含み,vの距離は0である.Uはv以外の頂点を含み、Uの頂点uの距離はエッジ上の重み(vとuにエッジがある場合)または
∞(uがvの出辺隣接点でなければ).
(2)Uから距離vが最も小さい頂点kを選択し、kをSに加える(この選択された距離がvからkまでの最短経路長である).
(3)kを新たに考慮した中間点とし,Uにおける各頂点の距離を修正する.ソース点vから頂点u(u U)までの距離(頂点kを通る)が元の距離(頂点kを通らない)よりも短い場合は、頂点uの距離値を修正し、修正後の距離値は頂点kの距離に上の重みを加える.
(4)すべての頂点がSに含まれるまで、ステップ(2)と(3)を繰り返す.
複雑度分析
Dijkstraアルゴリズムの時間的複雑度はO(n^2)である.
空間複雑度は記憶方式に依存し,隣接行列はO(n^2)である.
最短パスアルゴリズムのコードを次に示します.

              while(Visited.size() != Switches.size())
              {
                  for(int i = 0;i < alreadyVisited.size(); i ++)
                  {
                      ASwitch sw1 = (ASwitch)alreadyVisited.get(i);
                      System.out.println("already visited: "+sw1.SWName);
                      Vector ng = getNeighbors(topo, Switches, sw1);
                      alreadyVisited.remove(sw1);
                      //Visited.add(sw1);
                      Visited = addtoVector(Visited,sw1);
                      for(int j = 0;j < ng.size();j++)
                      {
                          ASwitch sw2 = (ASwitch)ng.get(j);
                          if((swValue.get(sw2) == 0) ) continue;
                          int tempcost = -1;
                          int tcost = getCost(topo, sw1, sw2, insid, "legacy");;
                          if(tcost >0 ) tempcost = swValue.get(sw1)+tcost;
                          if((tempcost > 0) && (tempcost < swValue.get(sw2)))
                          {
                              swValue.put(sw2, tempcost);
                              presw.put(sw2, sw1);
                              System.out.println("sw: "+sw2.SWName+"   cost: "+tempcost+"   presw: "+sw1.SWName);
                              
                              alreadyVisited.add(sw2);
         
                          }
                      }
                  }
              }