網(wǎng)絡(luò)工程師考點(diǎn)：圖的最短路徑應(yīng)用

圖的結(jié)構(gòu)－鄰接矩陣

// ---------------------- 圖的結(jié)構(gòu)：鄰接矩陣 --------------------------//

// 鄰接矩陣元素
typedef struct ArcCell{
  int adj;      // arc value: >0, INFINITY: no link
  char *info;      
}AcrCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

// 圖的結(jié)構(gòu)  
typedef struct{
  char vexs[MAX_VERTEX_NUM][5];    // 頂點(diǎn)數(shù)組
  AdjMatrix arcs;          // 鄰接矩陣
  int vexnum;            // 圖當(dāng)前的頂點(diǎn)數(shù)
  int arcnum;            // 圖當(dāng)前邊的個數(shù)
}MGraph;

// 建立鄰接圖（key=1為有向網(wǎng)，key=0為無向網(wǎng)）
Status createUDN(MGraph &G,int vexnum,int edgenum,char *names,char *edges,int key){
  int i,j,k,value;
  // 輸入當(dāng)前圖的頂點(diǎn)數(shù)，邊個數(shù)
  G.vexnum=vexnum;
  G.arcnum=edgenum;
  // 各個頂點(diǎn)數(shù)據(jù)
  for(i=0;i    for(j=0;j<4;j++){
      G.vexs[i][j]=*names;
      names++;
    }
    G.vexs[i][4]='\0';
  }
  // 初始化鄰接矩陣（全為INFINITY）
  for(i=0;i    for(j=0;j      G.arcs[i][j].adj=INFINITY;
      G.arcs[i][j].info=NULL;
      
    }
  }
  // 建立鄰接矩陣每條邊的數(shù)值
  for(k=0;k    i=int(*edges)-48;
    edges++;
    j=int(*edges)-48;
    edges++;
    value=(int(*edges)-48)*10;
    edges++;
    value+=int(*edges)-48;
    edges++;
    G.arcs[i][j].adj=value;
    if(!key){
      G.arcs[j][i].adj=value;
    }
  }
  return OK;
}

// 打印出鄰接矩陣
void PrintGraph(MGraph &G){
  int i,j;
  cout<<"\n//--------------- PrintMatrix -----------------//\n\n ";
  for(i=0;i    cout<}

求最短路徑程序

// ---------------------- 求源點(diǎn)v0到各點(diǎn)的最短路徑 --------------------------//

void ShortestPath(MGraph &G,int v0){
  int D[MAX_VERTEX_NUM],final[MAX_VERTEX_NUM],i,w,v=0,min;
  // 建立隊(duì)列數(shù)組，用以依次儲存最短的路徑
  LinkQueue Q[MAX_VERTEX_NUM];
  // 初始化數(shù)組
  for(i=0;i    InitQueue(Q[i]);
    D[i]=G.arcs[v0][i].adj;
    final[i]=false;
  }
  final[v0]=true;
  // 一個一個循環(huán)找出最短距離（共vexnum－1個）
  for(i=1;i    min=INFINITY;
    // 掃描找出非final集中最小的D[]
    for(w=0;w      if(!final[w] && D[w]        v=w;
        min=D[w];
      }
    }
    final[v]=true;
    // 更新各D[]數(shù)據(jù)
    for(w=0;w      if(!final[w] && G.arcs[v][w].adj+min        D[w]=G.arcs[v][w].adj+min;
        CopyQueue(Q[v],Q[w]);
        EnQueue(Q[w],v);
      }
    }
  }
  // 打印出結(jié)果
  cout<<"http://--------------- ShortestPath -----------------//\n\n";
  cout<<" 出發(fā)地->目的地\t最短距離\t詳細(xì)路徑\n\n";
  for(i=0;i    if(D[i]!=INFINITY){
      cout<<" "< "<      cout<      while(!EmptyQueue(Q[i])){
        DeQueue(Q[i],v);
        cout<<" -> "<      }
      cout<<" -> "<    }else{
      cout<<" "< "<      
    }
  }
  cout<<"\n//--------------- ShortestPath -----------------//\n\n\n";
}

主程序

void PrintCity(char *names,int vexnum){
  int i,j;
  cout<<"城市列表：\n\n";
  for(i=0;i    cout<<" "<    for(j=0;j<4;j++){
      cout<<*names;
      names++;
    }
    cout<<" ";
  }
  cout<<"\n請選擇出發(fā)城市 >";
}


void main(){
  MGraph G;

  // 圖的結(jié)構(gòu)數(shù)據(jù)
  char *edges,*names;
  int vexnum,arcnum,city,kind;
  vexnum=10;
  arcnum=14;
  names="鄭州北京天津南昌上海貴陽株洲廣州蘭州西寧";
  edges="01450235035012201591187024503450585056205750604063409835";

  // 用戶界面
  do{
    PrintCity(names,vexnum);
    cin>>city;
    cout<<"\n\n操作：\n0－無向圖列表 1－有向圖列表\n2－無向圖矩陣 3－有向圖矩陣\n4－選擇城市 5－退出\n\n請選擇操作 >";
    do{
      cin>>kind;
      if(kind>=0 && kind <=3){
        createUDN(G,vexnum,arcnum,names,edges,kind%2);
        switch(kind/2){
        case 0:ShortestPath(G,city);
          break;
        case 1:PrintGraph(G);
          break;
        }
      }
      cout<<"\n\n操作：\n0－無向圖列表 1－有向圖列表\n2－無向圖矩陣 3－有向圖矩陣\n4－選擇城市 5－退出\n\n請選擇操作 >";
    }
    while(kind<4);
  }
  while(kind<5);
}