• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 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ù)學》課程改革
    砚山县| 青海省| 安阳市| 靖宇县| 丰镇市| 巴青县| 玉溪市| 资阳市| 大埔区| 天津市| 天祝| 博白县| 白朗县| 平塘县| 舞钢市| 文安县| 盈江县| 阳朔县| 若尔盖县| 武鸣县| 樟树市| 抚松县| 宝丰县| 剑川县| 江西省| 武邑县| 萍乡市| 凤冈县| 尚志市| 吉木萨尔县| 洮南市| 鞍山市| 宜丰县| 沧源| 嵊泗县| 尚志市| 泰和县| 平邑县| 从江县| 缙云县| 新干县|