Dijkstra(迪杰斯特拉)最短路径算法

Dijkstra 算法的核心思想是通过逐步扩展最短路径来找到从起点到所有其他节点的最短距离。
求从一个顶点到其余各顶点的最短路径，解决的是有权无向图中最短路径问题

  1. 构造邻接矩阵 edge 记录图，需要初始化使各点间距离为无穷，与其本身距离为 0。
  2. 构造矩阵 visited 记录点是否已经纳入，在 dijkstra 算法开始时确定一个出发点并标记已拜访。
  3. 构建矩阵 dis 记录当前从出发点到各个点的最短路径，用于更新最短路，需初始化，理由同 1。

从出发点开始遍历，根据邻接矩阵更新 dis ，然后遍历 dis 寻找距离最短点，在 visited 标记已拜访，然后更新 dis ，假设点 p 到点 q，若 edge[p][q] + dis[p] < dis[q]，则更新。
因为每次都是最短路上做贪心算法，所以结果必定最小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int edge[105][105];
int dis[105];
int vis[105];
int vexnum;
void dijistra(int u,int v){
 for(int i=0;i<vexnum;i++){
  vis[i]=0;
  dis[i]=edge[u][i];
 }
 vis[u]=1;
 for(int i=0;i<vexnum-1;i++){
  int minn=inf;
  int pp;
  for(int j=0;j<vexnum;j++){
   if(vis[j]==0&&dis[j]<minn){
   minn=dis[j];
   pp=j;//刷新当前出发点
  }
 }
 vis[pp]=1;
 for(int j=0;j<vexnum;j++){
  if(vis[j]==0&&dis[pp]+edge[pp][j]<dis[j])//最短路
   dis[j]=dis[pp]+edge[pp][j];
  }
 }
 cout<<dis[v];
}
int main(){
 int n,m;cin>>n>>m;
 vexnum=n;
 for(int i=0;i<n;i++)
  for(int j=0;j<n;j++){
   if(i==j)edge[i][j]=0;
   else edge[i][j]=inf;
  }
 for(int i=1;i<=m;i++){
  int x1,x2,x3;
  scanf("%d%d%d",&x1,&x2,&x3);
  edge[x1][x2]=x3;
 }
 int end;cin>>end;
 dijistra(0,end);

 return 0;
}