图论——最短路——Dijkstra算法

  1. 云栖社区>
  2. 博客>
  3. 正文

图论——最短路——Dijkstra算法

小笨笨qaq 2018-11-07 20:18:00 浏览432
展开阅读全文

对图论有一定了解的人,一定知道最短路。

最短路算法一共有4中,严格来说是3种,应为最后一个是第3个的优化。

他们分别是:

Floyd、Dijkstra、Bellman-Ford和SPFA算法

Floyd是最暴力的思想,这里就不在阐述。

今天,我们来讲Dijkstra算法,中文名迪杰斯特拉。

Dijkstra是单源最短路,也就是计算从一点出发,到各个点的距离。

这是一个类似贪心的算法,是否流程如下:

1.初始化dist [ v0 ] = 0;(v0是源点),其余dist为INF(正无穷,通常用0x3f3f3f3f表示)

2.找出未标记的、dist [ x ] 的最小 x ,标记 x;

3.扫描节点x的所有 出边 (x,y,z)表示x到y有权值为z的边。,若dist [ y ] > dist [ x ] + z,则使用 dist [ x ] + z 更新 dist [ y ];

4.重复2~3,直到所有点都被标记。

dist [ x ] 就是 v0 到 x 的最短路径。

代码实现:

 1 int a[3010][3010]/**/,d[3010],n,m;
 2 bool v[3010];//是否被访问
 3 void dijkstra(int v0)//源点
 4 {
 5     memset(d,0x3f3f3f3f,sizeof(d));//距离
 6     memset(v,0,sizeof(v));//初始化都未访问
 7     d[v0]=0;
 8     for(int i=1;i<n;i++)//重复n-1次 
 9     {
10         int x=0;
11         //找到未标记的dist最小的节点
12         for(int j=1;j<=n;j++)
13             if(!v[j]&&(x==0||d[j]<d[x]))//j为访问或dist[j]<dist[x]; 
14                 x=j;
15         v[x]=1;
16         //用x更新其他点 
17         for(int y=1;y<=n;y++)
18             d[y]=min(d[y],d[x]+a[x][y]/*x到y的边权值*/); 
19     }
20 }

这就是模板of Dijkstra,很好理解,大家要是有不理解的,也可以查相关资料,去了解更多的知识。

网友评论

登录后评论
0/500
评论
小笨笨qaq
+ 关注