最短无向图的算法

Question

如需修改你的代码，申请加分100。参考：
Kenji Ikeda老前辈的实现程序（用Java语言）http://www.microsoft.com/china/community/Column/38.mspxhttp://carbon.cudenver.edu/~hgreenbe/sessions/dijkstra/DijkstraApplet.html

Answer 1

不好意思...我是想再给出的几个节点中，先用BFS遍历所有节点，然后两两相连（这个未在程序中实现），然后通过shortestPath方法选出最短的一条从指定起点(start)到指定终点(end)的路线并显示.整个通过一个队列实现节点的纪录.每个节点都有名字(label)和唯一的标号（id)，
这个矩阵用来表示无向图的连接关系（我没法把图放上来，对不住大伙儿了 :<  )   {0,1,1,1,0,1,0,0,},
{1,0,0,0,0,1,0,0,},
{1,0,0,1,1,0,0,0,},
{1,0,1,0,0,0,1,0,},
{0,0,1,0,0,0,1,1,},
{1,1,0,0,0,0,0,1,},
{0,0,0,1,1,0,0,1,},
{0,0,0,0,1,1,1,0,},
 
这个方法用于表示返回未遍历的矩阵中的某个坐标，若是-1，则不存在还没有遍历过的点
public int getAdjUnvisitedVertex(int v)
      {
      for(int j=0; j<nVerts; j++)
         if(matrix[v][j]==1 && vertexList[j].wasVisited==false)
            return j;
      return -1;
      }  // end getAdjUnvisitedVertex()这个方法用于寻找最短路径
 public void shortestPath(String start,String end)
   {
      int startID=0,endID=0;
      int n=nVerts;
      
      for(int i=0;i<nVerts;i++)   //id is impossible to be the same of different vertices
      {
       if(start.equals(vertexList[i].label))
         startID = vertexList[i].id;           //开始处节点的id号
      
       if(end.equals(vertexList[i].label))
           endID  = vertexList[i].id;             //结尾处节点的id号
      }      
      int j=endID;          //纪录结尾id准备倒插入track数组，然后正着输出 
      
      do
      {
       track[n]=j;         //倒插
       n--;                //下标纪录减一
       j=pre[j];           //让标记号成为前一个节点的id号
      
      }while(pre[j]!=startID);      //如果前一个节点的id号等于startID那么停止循环
      
      track[n]=startID;         //将STARTid 也插入track       
      for(int i=n;i<=nVerts;i++)       //输出track中存的数的对应节点的label
      {
    
     System.out.print(vertexList[ track[i] ].label+"---");
      } 
      
      System.out.println();
   }   
这是bfs遍历，细节不用我解释了吧？:)
  public void bfs(String start,String end)                   // breadth-first search
      { 
      int i;  // begin at vertex 0
     
      for(i=0;i<nVerts;i++)
      {
       if( vertexList[i].label.equals(start) )  //find out the first character suits the start point 
   {
       vertexList[i].wasVisited = true; //  it
       displayVertex(i);                // display it
       theQueue.insert(i);              // insert at tail
       break;
       }
      }
      
      int counter;               //这个遍量先别看，没用
      int v2;
      
      while( !theQueue.isEmpty() )     // until queue empty,
         {
         int v1 = theQueue.remove();   // remove vertex at head
         
         // until it has no unvisited neighbors
         while((v2=getAdjUnvisitedVertex(v1)) != -1 && !vertexList[v2].label.equals(end) )
            {                                  // get one,
            counter=v2;                       //不看
            //把counter--当作v2看，pre数组用于纪录前一个节点，我怀疑就是这里出了问 题            pre[counter--]=v1;          //怀疑就是这步有问题
            vertexList[v2].wasVisited = true;  //  it
            displayVertex(v2);                 // display it
            theQueue.insert(v2);      // insert it
            
            }   // end while
            
         }  // end while(queue not empty)      // queue is empty, so we're done
      for(int j=0; j<nVerts; j++)              // reset flags
         vertexList[j].wasVisited = false;
      }  // end bfs()