算法学习-最短路径算法算法学习-最短路径算法

65 阅读 0 评论 43 点赞

我是靠谱客的博主大胆书包，最近开发中收集的这篇文章主要介绍算法学习-最短路径算法算法学习-最短路径算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

算法学习-最短路径算法

Dijkstra算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。

它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

基本思想

通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。

此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是"起点s到该顶点的路径"。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。 ... 重复该操作，直到遍历完所有顶点。

以上是算法的思想，但理解起来比较困难，严蔚敏版数据结构书中讲得也比较抽象，在查找资料时，看到了一个比较详细的图解和介绍，链接为：http://www.cnblogs.com/skywang12345/p/3711512.html

经过一天的学习，才基本理解了算法的思想，在实现时参考了数据结构书上的算法。下面，给出自己编写的比较简单的算法。其中对图的定义可能不是很完整。

#include "iostream.h"
#define infinity 1000
//定义为无穷大，即不存在边
#define max 6
typedef struct graph
{
int vexs[max];
//顶点向量
int arcs[max][max];	//带权邻接矩阵
int vexnum,arcnum;	//顶点数目、边数目
}mgraph;
void shortpath_dij(mgraph g,int v0,int p[max][max],int d[max])
{
int final[max];
//已经求得从v0到v的最短路径时，置为1
for(int v=0;v<g.vexnum;++v)
//初始化
{
final[v]=0;
d[v]=g.arcs[v0][v];
//v0到v的距离
for(int w=0;w<g.vexnum;++w)
p[v][w]=0;
if(d[v]<infinity)
//距离不为无限大，即v0有边到v
{
p[v][v0]=1;p[v][v]=1;
}
}
final[v0]=1;d[v0]=0;
//初始点
for(int i=0;i<g.vexnum;++i)	//循环，求v0到每个点v的最短路径
{
int min=infinity;
for(int w=0;w<g.vexnum;++w)
{
if(!final[w])
if(d[w]<min)
//w点距离更近
{
v=w;min=d[w];
}
}
final[v]=1;
for(w=0;w<g.vexnum;++w)
//更新当前最短路径和距离
{
if(!final[w]&&(min+g.arcs[v][w]<d[w]))
{
d[w]=min+g.arcs[v][w];
for(int j=0;j<g.vexnum;++j)p[w][j]=p[v][j];
p[w][w]=1;
}
}
}
}
void main()
{
int p[max][max];
int d[max];
//初始化图
注意赋值的格式(调试此处出现多次错误)
mgraph m_g={{0,1,2,3,4,5},
{infinity,infinity,10,infinity,30,100,
infinity,infinity,5,infinity,infinity,infinity,
infinity,infinity,infinity,50,infinity,infinity,
infinity,infinity,infinity,infinity,infinity,10,
infinity,infinity,infinity,20,infinity,60,
infinity,infinity,infinity,infinity,infinity,infinity},6,8};
shortpath_dij(m_g,0,p,d);
for(int i=0;i<m_g.vexnum;++i)
{
for(int j=0;j<m_g.vexnum;++j)	//打印路径
{
cout<<p[i][j]<<" ";
}
cout<<d[i]<<" "<<endl;
//打印距离
}
}

初始化的带权有向图如图：