• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看

      ?

      Dijkstra算法設(shè)計與實現(xiàn)

      2016-12-21 11:00杜衡吉
      電腦知識與技術(shù) 2016年28期
      關(guān)鍵詞:最短路徑離散數(shù)學

      杜衡吉

      摘要:最短路徑算法在各領(lǐng)域應(yīng)用廣泛,大多《離散數(shù)學》的圖論部分最短路徑算法講解較為粗略,不便于學生學習和實踐。經(jīng)過多年教學總結(jié),對最短路徑算法給出設(shè)計和實現(xiàn),有利于學生對本知識的掌握和實踐應(yīng)用。

      關(guān)鍵詞:最短路徑;離散數(shù)學; Dijkstra算法

      中圖分類號:TP311 文獻標識碼:A 文章編號:1009-3044(2016)28-0079-02

      1 概述

      最短路徑問題是指在一個非負權(quán)值圖中找出兩個指定節(jié)點間的一條權(quán)值之和最小的路徑。Dijkstra 算法在很多計算機專業(yè)可均有介紹,如數(shù)據(jù)結(jié)構(gòu),離散數(shù)學等,但大都比較粗略。迪克斯特拉算法是經(jīng)典的求解最短路徑問題的方法,是按路徑長度遞增的次序來產(chǎn)生最短路徑的算法[1]。

      最短路徑問題描述:設(shè)n,m帶權(quán)圖 G=,V={v0,v1,…,vn-1},E={e1,e2,…,em},其中假設(shè)每條邊ei 的權(quán)值為 wi,單源的最短路徑就是從圖G中找到起源點 V0 到圖中其余各點的最短路徑。

      2 最短路徑概念

      帶權(quán)圖G=, 其中W:ER, eE,w(e)稱作e的權(quán)。 若vi和vj相鄰e=(vi,vj), 記w(vi,vj)=w(vi,vj) , 若vi,vj不相鄰, 記w(vi,vj)=。通路L的權(quán)是指L的所有邊的權(quán)值之和, 記作w(L),u和v之間的最短路徑指的是 u和v之間邊權(quán)最小的通路[2]。

      3 Dijkstra算法描述

      1)算法基本過程:設(shè)帶權(quán)圖G=,把圖G中頂點集合V分成兩個子集,第一個子集是已求出最短路徑的頂點集合,用V1表示,初始化時V1中只有一個起源點,以后每求得一條最短路徑 , 就將被選定點加入到集合V1中,直到圖中全部頂點都依次添加到到V1中,算法就結(jié)束了;第二個集合為G中其余未確定最短路徑的頂點集合,用V2表示,按最短路徑長度的遞增次序依次把第二個集合V2中的被選頂點加入集合V1中。特別,在加入的過程中,總保持從起源點v0到V1中各頂點的最短路徑長度不大于從源點v0到V2中任何頂點的最短路徑長度。此外,每個頂點對應(yīng)一個距離,V1中的頂點的距離就是從v0到此頂點的最短路徑長度,V2中的頂點的距離,是從v0到此頂點只包括V1中的頂點為中間頂點的當前最短路徑長度。

      2)算法具體步驟:

      a.初始時,V1只包含源點,即V1={ v0},v0的距離為0。V2包含除v0外的其他頂點,即: V2={ v1, v2…,vn-1}。定義集合V2中的頂點的距離:若v0與V2中頂點v有邊,則dist(v)=w(v0,v)正常有權(quán)值,若v0與v點不相鄰,則dist(v)= ∞。

      b.從V2中選取一個點k加入V1中,選擇公式dist(k)=min(dist(v) | v∈U),把k加入V1中(該選定的距離就是v0到k的最短路徑長度)。此時V1= V1∪{k},同時V2集合中刪除k點,即V2= V2-{k}。

      c.以k為新考慮的中間點,修改V2中各頂點的距離;若從源點v0到頂點v的距離(經(jīng)過頂點k)比原來距離短,則修改頂點 v的距離值,否則v的距離值不變,修改公式dist(v)=min{dist(v),dist(k)+dist(k,v)}[3]。

      d.重復步驟b和c直到V1=V,算法停止。

      4 算法實例

      1)先給出一個無向圖G=,如圖1所示:

      用Dijkstra算法找出以A為起點的單源最短路徑步驟如表1:

      5 算法代碼實現(xiàn)

      測試案例如圖2所示:

      #include

      #include

      #define M 100

      #define N 100

      using namespace std;

      typedef struct node

      {int m[N][M]; //鄰接矩陣

      int n; //頂點數(shù)

      int e; //邊數(shù)

      }MGraph;

      void Dpath(MGraph g,int *dist,int *path,int v0) //v0表示源點

      {int i,j,k;

      bool *ved=(bool *)malloc(sizeof(bool)*g.n);

      for(i=0;i

      {if(g.m[v0][i]>0&&i!=v0)

      {dist[i]=g.m[v0][i];

      path[i]=v0; } //path記錄最短路徑上從v0到i的前一個頂點

      else

      {dist[i]=INT_MAX; //若i不與v0直接相鄰,則權(quán)值置為無窮大

      path[i]=-1; }

      ved[i]=false;

      path[v0]=v0;

      dist[v0]=0; }

      ved[v0]=true;

      for(i=1;i

      {int min=INT_MAX;

      int u;

      for(j=0;j

      {if(ved[j]==false&&dist[j]

      { min=dist[j];

      u=j;} }

      ved[u]=true;

      for(k=0;k

      { if(ved[k]==false&&g.m[u][k]>0&&min+g.m[u][k]

      {dist[k]=min+g.m[u][k];

      path[k]=u; }}}}

      void Apath(int *path,int v,int v0) //打印最短路徑上的各個頂點

      {stack s;

      int u=v;

      while(v!=v0)

      { s.push(v);

      v=path[v]; }

      s.push(v);

      while(!s.empty())

      {cout<

      s.pop();}}

      int main(int argc, char *argv[])

      { int n,e; //表示輸入的頂點數(shù)和邊數(shù)

      while(cin>>n>>e&&e!=0)

      {int i,j;

      int s,t,w; //表示存在一條邊s->t,權(quán)值為w

      MGraph g;

      int v0;

      int *dist=(int *)malloc(sizeof(int)*n);

      int *path=(int *)malloc(sizeof(int)*n);

      for(i=0;i

      for(j=0;j

      g.m[i][j]=0;

      g.n=n;

      g.e=e;

      for(i=0;i

      {cin>>s>>t>>w;

      g.m[s][t]=w; }

      cin>>v0; //輸入源頂點

      Dpath(g,dist,path,v0);

      for(i=0;i

      {if(i!=v0)

      { Apath(path,i,v0);

      cout<

      return 0; }

      測試結(jié)果如圖3所示:

      6 小結(jié)

      作為一門計算機的專業(yè)基礎(chǔ)課《離散數(shù)學》在計算機學科領(lǐng)域中發(fā)揮了重要的作用。最短路徑算法在很多方面有著重要的應(yīng)用,針對教材中Dijkstra最短路徑算法講解粗略,學生學習困難等問題,本人結(jié)合多年的教學經(jīng)驗,對Dijkstra算法求最短路徑給出了詳細的算法設(shè)計和實現(xiàn),對這部分內(nèi)容的教學幫助明顯。

      參考文獻:

      [1] 李妍妍.Dijkstra最短路徑分析算法的優(yōu)化實現(xiàn)[J].測繪與空間地理信息,2014,37(5):172-190.

      [2] 耿素云,屈婉玲,張立昂.離散數(shù)學[M]. 5版.北京:清華大學出版社,2013:128-130.

      [3] 曹曉東,原旭.離散數(shù)學及算法 [M].北京:機械工業(yè)出版社,2012:240-244.

      猜你喜歡
      最短路徑離散數(shù)學
      一位合格的離散數(shù)學教師所應(yīng)具備的能力
      離散數(shù)學實踐教學探索
      獨立學院離散數(shù)學教學改革探討
      基于實踐教學的《離散數(shù)學》課程改革
      墨竹工卡县| 时尚| 建湖县| 太和县| 沙湾县| 石渠县| 甘泉县| 呼玛县| 新疆| 扬中市| 连山| 德惠市| 罗山县| 游戏| 昌平区| 奉贤区| 重庆市| 仲巴县| 互助| 凤山市| 丁青县| 尼木县| 静海县| 宁明县| 昌宁县| 忻城县| 苍溪县| 东乌| 玉山县| 合肥市| 盘山县| 石狮市| 庆城县| 涿州市| 华安县| 元江| 安新县| 佛学| 安岳县| 蓬安县| 湘潭市|