本文共 2828 字，大约阅读时间需要 9 分钟。
今天学长给我们讲了求最短路的4种算法以及它们具体的应用。然后今晚写了好久才把第一个dijkstra算法写好。。。。。。。。
对于dijkstra算法共有3个版本：基础版及用优先队列,堆进行优化的版本。
对于基本版的算法，其实我觉得它和求最小生成树的prime()算法很是类似,无论是从思想还是代码的实现上。
我把它的代码分为2个部分,第一部分是初始化:包括dist数组，visited数组。第二部分是在n次循环的过程中
利用贪心的实现每次找到一个dist值最小的顶点,然后标记,然后再对和这个顶点相连的其它顶点的dist值进行
修改。这个思路的时间复杂度为n^2。
具体代码如下：
#include #include #include using namespace std;#define Max 100#define INF 1<<30 //不要用0x7fffffff表示最大值 //fa[]数组存储每个顶点的父节点好用于打印路径 int fa[Max],visited[Max],dist[Max]; //dist数组用来保存每个点到源点的最短路径长度 int map[Max][Max];int n,m; //n个顶点m条边的有向图 void dijkstra(int s) //s开始的单源最短路 { int i,j,k; for(i=0;i >n>>m) { Init(); for(i=0;i >k1>>k2>>w; map[k1][k2]=w; } dijkstra(0); for(i=0;i
第二种思路是用邻接表和优先队列对上面的代码实行优化。具体的优化有两个地方:第一个是利用优先队列的性质
优化寻找具有最小dist值顶点i的过程；这个需要自定义一个小整数优先的优先队列,定义好后，每次寻找只需要一个p.top()就行。第二个是用邻接表优化对i的邻结点的访问；用邻接矩阵表示图的时候对每一个顶点都要试探一下是不是
i的邻结点,而用邻接表表示后就能保证只访问i的邻结点而不会有多余的试探了。经过这两个优化后，算法的时间复杂度就降为mlongn了(m是边数)。所以这种算法适用于边比较少的稀疏图，不过刘汝佳讲无论边多不多，反正下面这个
都要比上面那个快。。。。。。。。
代码如下：
#include #include #include #include #include //使用pair的头文件using namespace std;#define INF 1<<30#define Max 1000int n,m;int fa[Max],visited[Max],dist[Max];int first[Max],u[Max],v[Max];int w[Max],next[Max];typedef pair pii; //定义此类型配合优先队列的使用priority_queue ,greater >q; //定义了一个pill型,小整数优先的优先队列void dijkstra(int s){ int i,j,k; for(i=0;i dist[x]+w[e]) // 第e条边(即以x为起点,v[e]为终点的边的权值可直接由w[e]得) { dist[v[e]]=dist[x]+w[e]; //更新dist fa[v[e]]=x; //更新父节点信息 q.push(make_pair(dist[v[e]],v[e])); //将更新过的顶点入队 } } } int main(){ int i,j,k; while(cin>>n>>m) { for(i=0;i >u[e]>>v[e]>>w[e];//输入第e条边的起点 终点 权值 next[e]=first[u[e]]; //头插法 first[u[e]]=e; } dijkstra(0); for(i=0;i
对于第3种利用堆进行优化的代码和上面第2种很像,主要好像是省了一个visited[]标记数组；但是虽然代码我写
出来了,但原理还是不太懂,明天还得请教一下
代码如下：
#include #include #include #include #include //使用pair的头文件using namespace std;#define INF 1<<30#define Max 1000int n,m;int fa[Max],visited[Max],dist[Max];int first[Max],u[Max],v[Max];int w[Max],next[Max];typedef pair pii; priority_queue ,greater >q; void dijkstra(int s){ int i,j,k; for(i=0;i dist[q.top().second]) q.pop(); //这一句是堆优化的关键之处,应该是可以避免重复访问,但现在我还不是太了解原理 if(q.empty()) break; pii u=q.top();q.pop();//取出dist值最小的点 int x=u.second; //取出dist值最小点的顶点编号 for(int e=first[x];e!=-1;e=next[e]) //邻接表主要用来优化寻找从x出发的边这一步 if(dist[v[e]]>dist[x]+w[e]) // 第e条边(即以x为起点,v[e]为终点的边的权值可直接由w[e]得) { dist[v[e]]=dist[x]+w[e]; //更新dist fa[v[e]]=x; //更新父节点信息 q.push(make_pair(dist[v[e]],v[e])); //将更新过的顶点入队 } } } int main(){ int i,j,k; while(cin>>n>>m) { for(i=0;i >u[e]>>v[e]>>w[e];//输入第e条边的起点 终点 权值 next[e]=first[u[e]]; //头插法 first[u[e]]=e; } dijkstra(0); for(i=0;i
转载地址：http://qhefb.baihongyu.com/