熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

第四部分 圖[7]

2022-06-13   來源: 數據結構 

    最短路徑
  
   迪傑斯特拉算法
  void ShortestPath_DIJ(Mgraph G int v PathMatrix &p ShortPathTable &D){
  //用Dijkstra算法求向網珠舁頂點到其余頂點v的最短路徑p[v]及其帶權長度d[v]
  //若p[v][w]為TRUE則w是從v到v當前求得最短路徑上的頂點
  //final[v]為true當且僅當vs已經求得v到v的最短路徑
  for(v=;v<Gvexnum;++v){
  inal[v]=FALSE; D[v]=Garcs[v][v];
  for(w=;w<Gvexnum;++w) p[v][w]=FALSE;//設空路徑
  if(D[v]<INFINITY){P[V][V]=TRUE;p[v][v]=TRUE;}
  }//for
  D[v]=; final[v]=TRUE;
  //開始主循環每次求得V到某個V頂點的最短路徑並加V到S集
  for(i=;i<Gvexnum;++i){
  min=INFINITY;
  for(w=;w<Gvexnum;++w)
  if(!final[w])
  if(D[w]<min) {v=w;min=D[w];}
  final[v]=TRUE;
  for(w=;w<Gvexnum;++w)
  if(!final[w]&&(min+Garcs[v][w]<D[w])){
  d[w]=min+Garcs[v][w];
  P[w]=P[v];
  p[w][w]=TRUE;
  }if
  }//for
  }ShortestPath_DIJ

    返回《數據結構》考研復習精編

[]  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23293.html
  • 上一篇文章:

  • 下一篇文章:
  • 推薦文章
    Copyright © 2005-2022 電腦知識網 Computer Knowledge   All rights reserved.