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

公司主營業(yè)務：網(wǎng)站設計、成都做網(wǎng)站、移動網(wǎng)站開發(fā)等業(yè)務。幫助企業(yè)客戶真正實現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。創(chuàng)新互聯(lián)公司是一支青春激揚、勤奮敬業(yè)、活力青春激揚、勤奮敬業(yè)、活力澎湃、和諧高效的團隊。公司秉承以“開放、自由、嚴謹、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領域給我們帶來的挑戰(zhàn)，讓我們激情的團隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)公司推出江干免費做網(wǎng)站回饋大家。

某個源點到其余各頂點的最短路徑

這個算法最開始心里怕怕的，不知道為什么，花了好長時間弄懂了，也寫了一遍，又遇到時還是出錯了，今天再次寫它，心里沒那么怕了，耐心研究，懂了之后會好開心的，哈哈

Dijkstra算法：

圖G

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

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

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

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

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

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

過程：

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

（2）.求出到j點的最短路徑，j點為不在S集合中的某點

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

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

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

（4）.重復（2）.（3）操作共n-1次，每次操作，在（2）得到一個到

某點的最短路徑。

有向圖求最短路徑

#include
#include 
#include
#define max 900000000
//有向圖 
int main(){
  int n,m,a,b,v,i,j,min,k;
  scanf("%d%d",&n,&m);//輸入n個頂點，m條邊 
  int g[n+1][n+1],d[n+1],vis[n+1];//g[i][j]表示i到j的邊的權值,vis[i]表示到此頂點的最短路是否已經(jīng)找到，d[i]當前源點到i頂點的最短路徑 
  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;id[k]+g[k][j]&&vis[j]==0){//經(jīng)過此k點到達j點的路徑是否小于其他到達j點的路徑 
        d[j]=d[k]+g[k][j];
      }
    }
  }  
  for(i=2;i<=n;i++){//輸出到達個點的最短路徑 
    printf("%d\n",d[i]);
  }
  return 0;
}

無向圖求最短路徑

無向圖也是相同思路：在構造鄰接矩陣時考慮對稱就行。

無向圖求最短路徑且有路徑輸出

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

建立一個新的結(jié)構體類型path，該類型變量d表示到達某點的最短路徑距離 ，該類型變量pre表示該最短路徑是經(jīng)過哪個點傳過來的

#include
#include 
#include
#define max 900000000
typedef struct{ 
  int d;//到達某點的最短路徑距離 
  int pre;//該最短路徑是經(jīng)過哪個點傳過來的，源點或其他某個點 
}path;
//有向圖 
int main(){
  int n,m,a,b,v,i,j,min,k,from;
  scanf("%d%d",&n,&m);//輸入n個頂點，m條邊 
  int g[n+1][n+1],vis[n+1];//g[i][j]表示i到j的邊的權值,vis[i]表示到此頂點的最短路是否已經(jīng)找到，d[i]當前源點到i頂點的最短路徑 
  path to[n+1];//記錄當前到某個點的最短路徑以及從哪個點傳過來的 
  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;ito[k].d+g[k][j]&&vis[j]==0){//經(jīng)過此k點到達j點的路徑是否小于其他到達j點的路徑 
        to[j].d=to[k].d+g[k][j];
        to[j].pre=k;//改變j點是誰傳來的，現(xiàn)在到j點的最短路徑是經(jīng)過k點的，由j點傳來 
      }
    }
  }  
  for(i=2;i<=n;i++){//輸出到達個點的最短路徑 
    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)容對大家有所幫助，如果還想學習更多知識，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道！