Dijkstra算法最短路徑的示例分析-創(chuàng)新互聯(lián)

小編給大家分享一下Dijkstra算法最短路徑的示例分析，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

成都網(wǎng)絡(luò)公司-成都網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)十載經(jīng)驗(yàn)成就非凡，專(zhuān)業(yè)從事成都做網(wǎng)站、成都網(wǎng)站制作、成都外貿(mào)網(wǎng)站建設(shè)，成都網(wǎng)頁(yè)設(shè)計(jì)，成都網(wǎng)頁(yè)制作，軟文平臺(tái)，一元廣告等。十載來(lái)已成功提供全面的成都網(wǎng)站建設(shè)方案，打造行業(yè)特色的成都網(wǎng)站建設(shè)案例，建站熱線：028-86922220，我們期待您的來(lái)電！

某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑

這個(gè)算法最開(kāi)始心里怕怕的，不知道為什么，花了好長(zhǎng)時(shí)間弄懂了，也寫(xiě)了一遍，又遇到時(shí)還是出錯(cuò)了，今天再次寫(xiě)它，心里沒(méi)那么怕了，耐心研究，懂了之后會(huì)好開(kāi)心的，哈哈

Dijkstra算法：

圖G

如圖：若要求從頂點(diǎn)1到其余各頂點(diǎn)的最短路徑，該咋求；

迪杰斯特拉提出“按最短路徑長(zhǎng)度遞增的次序”產(chǎn)生最短路徑。

首先，在所有的這些最短路徑中，長(zhǎng)度最短的這條路徑必定只有一條弧，且它的權(quán)值是從源點(diǎn)出發(fā)的所有弧上權(quán)的最小值，例如：在圖G中，從源點(diǎn)1出發(fā)有3條弧，其中以弧（1，2）的權(quán)值為最小，因此，（1，2）不僅是1到2的一條最短路徑，并且它可能是源點(diǎn)到其它各個(gè)終點(diǎn)的最短路徑中的一條子路徑。

其次，第二條長(zhǎng)度次短的最短路徑只可能有兩種情況：①它或者只含一條從源點(diǎn)出發(fā)的弧且弧上的權(quán)值大于已求得最短路徑的那條弧的權(quán)值，但小于其他從源點(diǎn)出發(fā)的弧上的權(quán)值②它或者是一條只經(jīng)過(guò)已求得最短路徑的頂點(diǎn)的路徑。

例如圖G中，從1到其他各點(diǎn)。過(guò)程中，用d[i]保存從1到i的的最短路徑（過(guò)程會(huì)變化），初值為：若源點(diǎn)到該源點(diǎn)有弧，則為權(quán)值，否則初始化為無(wú)窮大，每求得一條到達(dá)某個(gè)終點(diǎn)i的最短路徑，就繼續(xù)檢查是否存在以此路徑為子路徑的到達(dá)其他點(diǎn)的最短路徑，若存在，判斷其長(zhǎng)度是否比當(dāng)前求得的路徑長(zhǎng)度短，若短，就更新為更短的長(zhǎng)度。

如圖G中，求得到2的最短路徑d[2]為10，就把d[2]作為與2相連的到其他點(diǎn)的子路徑繼續(xù)檢查，得到到3的最短路徑為d[2]+50=60

過(guò)程：

（1）.令S={1}，S集合中表示已經(jīng)找到最短路徑的結(jié)點(diǎn)，開(kāi)始時(shí)1為源點(diǎn)，并設(shè)定d[i]的初始值為：d[i]=(1,i),

（2）.求出到j(luò)點(diǎn)的最短路徑，j點(diǎn)為不在S集合中的某點(diǎn)

d[j]=min{d[i]}

（3）.判斷所有沒(méi)在S集合中的頂點(diǎn)k，若d[k]>d[j]+(j,k)則修改d[k]的值為：

d[k]=d[j]+(j,k)

（4）.重復(fù)（2）.（3）操作共n-1次，每次操作，在（2）得到一個(gè)到

某點(diǎn)的最短路徑。

有向圖求最短路徑

#include<stdio.h>
#include<string.h> 
#include<stdlib.h>
#define max 900000000
//有向圖 
int main(){
  int n,m,a,b,v,i,j,min,k;
  scanf("%d%d",&n,&m);//輸入n個(gè)頂點(diǎn)，m條邊 
  int g[n+1][n+1],d[n+1],vis[n+1];//g[i][j]表示i到j(luò)的邊的權(quán)值,vis[i]表示到此頂點(diǎn)的最短路是否已經(jīng)找到，d[i]當(dāng)前源點(diǎn)到i頂點(diǎn)的最短路徑 
  memset(vis,0,sizeof(vis));
  for(i=0;i<=n;i++){ 
    for(j=0;j<=n;j++){
      g[i][j]=max;
    }
    d[i]=max;  
  }
  for(i=0;i<m;i++){//i到j(luò)的邊權(quán)值儲(chǔ)存到g鄰接矩陣中,i點(diǎn)到j(luò)點(diǎn)無(wú)直接相連的邊時(shí)，g[i][j]=max 
    scanf("%d%d%d",&a,&b,&v);
    g[a][b]=v;
  }
  for(i=2;i<=n;i++){
      d[i]=g[1][i]; //初始化源點(diǎn)到i點(diǎn)邊權(quán)值，之后過(guò)程中會(huì)發(fā)生變化 
  }
  vis[1]=1;
  for(i=2;i<=n;i++){//共循環(huán)n-1次，每循環(huán)一次，確定一條最短路，再次循環(huán)時(shí)這條路就不用考慮了，去尋找下一條最短路 
    min=max;
    for(j=2;j<=n;j++){//尋找下一條當(dāng)前最短路 
      if(d[j]<min&&vis[j]==0){
       min=d[j];
       k=j;
      }  
    }
    vis[k]=1;//找到了，到k點(diǎn)的路是當(dāng)前最短路，標(biāo)記它，根據(jù)它尋找下一條最短路 
    for(j=2;j<=n;j++){
      if(d[j]>d[k]+g[k][j]&&vis[j]==0){//經(jīng)過(guò)此k點(diǎn)到達(dá)j點(diǎn)的路徑是否小于其他到達(dá)j點(diǎn)的路徑 
        d[j]=d[k]+g[k][j];
      }
    }
  }  
  for(i=2;i<=n;i++){//輸出到達(dá)個(gè)點(diǎn)的最短路徑 
    printf("%d\n",d[i]);
  }
  return 0;
}

無(wú)向圖求最短路徑

無(wú)向圖也是相同思路：在構(gòu)造鄰接矩陣時(shí)考慮對(duì)稱(chēng)就行。

無(wú)向圖求最短路徑且有路徑輸出

在求最短路的過(guò)程中，最短路①它或者是從源點(diǎn)出發(fā)的?、谒蛘呤且粭l經(jīng)過(guò)已到其他最短路徑的頂點(diǎn)的路徑。

建立一個(gè)新的結(jié)構(gòu)體類(lèi)型path，該類(lèi)型變量d表示到達(dá)某點(diǎn)的最短路徑距離 ，該類(lèi)型變量pre表示該最短路徑是經(jīng)過(guò)哪個(gè)點(diǎn)傳過(guò)來(lái)的

#include<stdio.h>
#include<string.h> 
#include<stdlib.h>
#define max 900000000
typedef struct{ 
  int d;//到達(dá)某點(diǎn)的最短路徑距離 
  int pre;//該最短路徑是經(jīng)過(guò)哪個(gè)點(diǎn)傳過(guò)來(lái)的，源點(diǎn)或其他某個(gè)點(diǎn) 
}path;
//有向圖 
int main(){
  int n,m,a,b,v,i,j,min,k,from;
  scanf("%d%d",&n,&m);//輸入n個(gè)頂點(diǎn)，m條邊 
  int g[n+1][n+1],vis[n+1];//g[i][j]表示i到j(luò)的邊的權(quán)值,vis[i]表示到此頂點(diǎn)的最短路是否已經(jīng)找到，d[i]當(dāng)前源點(diǎn)到i頂點(diǎn)的最短路徑 
  path to[n+1];//記錄當(dāng)前到某個(gè)點(diǎn)的最短路徑以及從哪個(gè)點(diǎn)傳過(guò)來(lái)的 
  memset(vis,0,sizeof(vis));
  for(i=0;i<=n;i++){ 
    for(j=0;j<=n;j++){
      g[i][j]=max;
    }
    to[i].d=max;  
  }
  for(i=0;i<m;i++){//i到j(luò)的邊權(quán)值儲(chǔ)存到g數(shù)組中,i點(diǎn)到j(luò)點(diǎn)無(wú)直接相連的邊時(shí)，g[i][j]=max 
    scanf("%d%d%d",&a,&b,&v);
    g[a][b]=v;
    g[b][a]=v;
  }
  for(i=2;i<=n;i++){
      to[i].d=g[1][i]; //初始化源點(diǎn)到i點(diǎn)邊權(quán)值，之后過(guò)程中會(huì)發(fā)生變化 
      if(g[1][i]!=max){
       to[i].pre=1; 
      } 
  }
  vis[1]=1;
  for(i=2;i<=n;i++){//共循環(huán)n-1次，每循環(huán)一次，確定一條最短路，再次循環(huán)時(shí)這條路就不用考慮了，去尋找下一條最短路 
    min=max;
    for(j=2;j<=n;j++){//尋找下一條當(dāng)前最短路 
      if(to[j].d<min&&vis[j]==0){
       min=to[j].d;
       k=j;
      }  
    }
    vis[k]=1;//找到了，到k點(diǎn)的路是當(dāng)前最短路，標(biāo)記它，根據(jù)它尋找下一條最短路 
    for(j=2;j<=n;j++){
      if(to[j].d>to[k].d+g[k][j]&&vis[j]==0){//經(jīng)過(guò)此k點(diǎn)到達(dá)j點(diǎn)的路徑是否小于其他到達(dá)j點(diǎn)的路徑 
        to[j].d=to[k].d+g[k][j];
        to[j].pre=k;//改變j點(diǎn)是誰(shuí)傳來(lái)的，現(xiàn)在到j(luò)點(diǎn)的最短路徑是經(jīng)過(guò)k點(diǎn)的，由j點(diǎn)傳來(lái) 
      }
    }
  }  
  for(i=2;i<=n;i++){//輸出到達(dá)個(gè)點(diǎn)的最短路徑 
    printf("%d ",to[i].d);
    printf("%d ",i);
    j=i;
    while(j!=1){
      j=to[j].pre;
      printf("%d ",j);
    }
    printf("\n");
  }
  return 0;
}

以上是“Dijkstra算法最短路徑的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司行業(yè)資訊頻道！

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站muchs.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿(mǎn)足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。

名稱(chēng)欄目：Dijkstra算法最短路徑的示例分析-創(chuàng)新互聯(lián)
網(wǎng)站地址：http://muchs.cn/article40/ideho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動(dòng)網(wǎng)站建設(shè)、動(dòng)態(tài)網(wǎng)站、自適應(yīng)網(wǎng)站、面包屑導(dǎo)航、外貿(mào)網(wǎng)站建設(shè)、外貿(mào)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)