注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mihooke's blog

IT之恋

 
 
 

日志

 
 

Dijkstra算法细谈  

2014-08-01 22:21:54|  分类: 学习录 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

    Dijkstra算法是求从一个源点到其他各点的最短路径问题的。它的关键思想很简单,就是从源点出发,逐层遍历各个点,寻找路径最短的方案。

      算法是这样设计的:带权值有向图G=(V,E)设两个顶点的集合STS存放已找到的最短路径的顶点,T就等于V-S。初始状态,S={v0},然后不断从集合T中选渠道顶点v0路径最短的顶点u加入到S中,集合S每加入一个顶点,都要修改v0T中剩余顶点的最短路径长度,那么T中各顶点新的最短路径长度就等于原来的最短路径长度与顶点u的最短路径那个长度 加上 u到该顶点的路径长度值中最小值。不断循环此过程,直到T中顶点全部加到S中为止。若两个顶点之间没有路径。那么这两个顶点之间权值就设为,无穷大。

举个例子来说明下就一目了然了。

如下图是一个带权值的有向图。

Dijkstra算法细谈 - mihooke - mihooke的博客
 

初始状态S={v0}T={v1,v2,v3,v4}v0为中间点,有

v0->v1 = 10     //权值最小,路径最短

v0->v2 = ∞

v0->v3 = 30

v0->v4 = 100

很显然,把顶点v1存放到S中。

那么,S={v0,v1}T={v2,v3,v4},以v1为中间点,有

v0->v1->v2 = 60

v0->v3 = 30 < 60,所以顶点v3存放到S中。

那么,S={v0,v1,v3}T={v2,v4},以v3为中间点,有

v0->v3->v2 = 50    //权值最小

v0->v3->v4 = 90

接着把v2存放到S中。

此时,S={v0,v1,v2,v3}T={v4},以v2为中间点,有

v0->v1->v2->v4 = 70

v0->v3->v2->v4 = 60    //权值最小

此时S中就包含V中全部顶点了,遍历完毕。算法结束。

用代码实现的时候,引入一个向量D[i],它表示找到的v0到每个顶点的最短路径。那么D[j] = min{D[i] | vi∈V-S}

D[i]要么为顶点v0vi之间的权值,要么为D[k]和顶点vkvi的权值之和。假设有向图用邻接矩阵存储,如下:

 

 

V0

V1

V2

V3

V4

V0

10

30

100

V1

50

V2

10

V3

20

60

V4

arcs[i][j]表示弧<vi,vj>上的权值,那么从v0出发到其余各点vi可能达到最短路径长度的初值为:

D[i] = arcs[LocateVertex(G,v0)][i]  vi∈V-S

选择Vj,使得:

D[j] = min{D[i] | vi∈V-S}

修改D[k]D[k] = D[j]+arcs[j][k]

以下是实现算法代码。


#define INFINITY 3000

#define MaxVertexNum 30

#define true 1

#define false 0

void Dijkstra(MGraph G,int v0,int p[],int d[])

{

//p[v]表示v的前驱顶点

   int i,j,v,w;

   int min;

   int final[MaxVertexNum];//true表示找到最短路径

   for(v=0;v<G.vertexNum-1;v++)

   {//n-1个顶点遍历

      final[v]=flase;

      d[v]=G.arcs[v0][v];

      p[v]=-1;//表示没有前驱

      if(d[v]<INFINITY)

p[v]=v0;

   }

   d[v]=0;

   final[v0]=true;

   for(i=1;i<G.vertexNum;i++)

   {//开始主循环

      v=-1;

      min=INFINITY;

      for(w=0;w<=G.vertexNum-1;w++)//寻找离v0最近的顶点

if(!final[w] && (d[w]<min))

       {

 v=w;

 min=d[w];

       }

       if(v==-1)

 break;//表明v0到所有顶点的最短路径找到了

       final[v]=true;//v存放到S

       for(w=0;w<G.vertexNum-1;w++)//更新最短路径

 if(!final[w] && (min+G,arcs[v][w]<d[w]))

 {

    d[w]=min+G.arcs[v][w];

    p[w]=v;//修改v的前驱

 }

   }

}

总的来说,Dijsktra算法执行简单但很费时间,时间主要在两个for循环中,所以时间复杂度就是O(n^2)


附:

//打印各个最短路径代码

void shortpath_print(MGraph G,int v0,int p[],int d[])

{

   int i,j,v;

   for(v=0;v<G.vertexNum-1;v++)

   {

      if(p[v]==-1)

      continue;

      printf("%-4d",d[v]);

      printf("%d<-",v);

      i=v;

      while(p[i]!=-1)

     {

printf("%d<-",p[i]);

i=p[i];

     }

      printf("\n");

   }

}

//邻接矩阵存储

typedef struct {

   VertexType vertex[MaxVertexNum];

   Edgetype arcs[MaxVertexNum][MaxVertexNum];

   int vertexNum,edgeNum;

}MGraph;

  评论这张
 
阅读(48)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017