簡述dijkstra算法原理_Dijkstra算法圖文詳解

Dijkstra算法圖文詳解

釋出時間：2018-11-20 09:19,

浏覽次數：1238

, 标簽：

Dijkstra

Dijkstra算法

Dijkstra算法算是貪心思想

實作的，首先把起點到所有點的距離存下來找個最短的，然後松弛一次再找出最短的，所謂的松弛操作就是，周遊一遍看通過剛剛找到的距離最短的點作為中轉站會不會更近，如果更近了就更新距離，這樣把所有的點找遍之後就存下了起點到其他所有點的最短距離。

問題引入：

指定一個點(源點)到其餘各個頂點的最短路徑，也叫做“單源最短路徑”。例如求下圖中的1号頂點到2、3、4、5、6号頂點的最短路徑。

下面我們來模拟一下：

這就是Dijkstra算法的基本思路：

接下來是代碼：

已經把幾個過程都封裝成了基本子產品：

#include #include #include #include

#define Inf 0x3f3f3f3f using namespace std; int map[1005][1005]; int

vis[1005],dis[1005]; int n,m;//n個點，m條邊 void Init () {

memset(map,Inf,sizeof(map)); for(int i=1;i<=n;i++) { map[i][i]=0; } } void

Getmap() { int u,v,w; for(int t=1;t<=m;t++) { scanf("%d%d%d",&u,&v,&w);

if(map[u][v]>w) { map[u][v]=w; map[v][u]=w; } } } void Dijkstra(int u) {

memset(vis,0,sizeof(vis)); for(int t=1;t<=n;t++) { dis[t]=map[u][t]; }

vis[u]=1; for(int t=1;t

if(!vis[i]&&dis[i]

i=1;i<=n;i++) { if(map[temp][i]+dis[temp]

dis[i]=map[temp][i]+dis[temp]; } } } } int main() { scanf("%d%d",&m,&n);

Init(); Getmap(); Dijkstra(n); printf("%d\n",dis[1]); return 0; }