posts - 195,  comments - 30,  trackbacks - 0
 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

问题描述

  在无向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到由顶点 V0 到其余各点的最短路径。(单源最短路径 


 迪杰斯特拉(Dijkstra)算法思想
  
按路径长度递增次序产生最短路径算法:
  把V分成两组:
  (1)S:已求出最短路径的顶点的集合
  (2)V-S=T:尚未确定最短路径的顶点集合
  将T中顶点按最短路径递增的次序加入到S中,
  保证:(1)从源点V0到S中各顶点的最短路径长度都不大于
  从V0到T中任何顶点的最短路径长度
  (2)每个顶点对应一个距离值
  S中顶点:从V0到此顶点的最短路径长度
  T中顶点:从V0到此顶点的只包括S中顶点作中间
  顶点的最短路径长度
  依据:可以证明V0到T中顶点Vk的最短路径,或是从V0到Vk的
  直接路径的权值;或是从V0经S中顶点到Vk的路径权值之和
  (反证法可证)
  求最短路径步骤
  算法步骤如下:
  1. 初使时令 S={V0},T={其余顶点},T中顶点对应的距离值
  若存在<V0,Vi>,d(V0,Vi)为<V0,Vi>弧上的权值
  若不存在<V0,Vi>,d(V0,Vi)为∝
  2. 从T中选取一个其距离值为最小的顶点W且不在S中,加入S
  3. 对T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的
  距离值比不加W的路径要短,则修改此距离值
  重复上述步骤2、3,直到S中包含所有顶点,即S=T为止 

代码: 源地址:www.cnblogs.com/newwy 

/*********************************
*   最短路径---Dijkstra算法实现 
*      HDU:2544 
*   BLOG:www.cnblogs.com/newwy
*   AUTHOR:Wang Yong
*********************************
*/
#include <iostream>
#define MAX 100
#define INF 1000000000
using namespace std;
 int dijkstra (int mat[][MAX],int n, int s,int f)
 {
     int dis[MAX];
     int mark[MAX];//记录被选中的结点 
     int i,j,k = 0;
     for(i = 0 ; i < n ; i++)//初始化所有结点,每个结点都没有被选中 
         mark[i] = 0;
    for(i = 0 ; i < n ; i++)//将每个结点到start结点weight记录为当前distance 
    {
        dis[i] = mat[s][i];
        //path[i] = s;
    }
    mark[s] = 1;//start结点被选中 
    
//path[s] = 0;
    dis[s] = 0;//将start结点的的距离设置为0 
    int min ;//设置最短的距离。 
    for(i = 1 ; i < n; i++)
    {
        min = INF;
        for(j = 0 ; j < n;j++)
        {
            if(mark[j] == 0  && dis[j] < min)//未被选中的结点中,距离最短的被选中 
            {
                min = dis[j] ;
                k = j;
            }
        }
        mark[k] = 1;//标记为被选中 
        for(j = 0 ; j < n ; j++)
        {
            if( mark[j] == 0  && (dis[j] > (dis[k] + mat[k][j])))//修改剩余结点的最短距离 
            {
                dis[j] = dis[k] + mat[k][j];
            }
        }
    }
    return dis[f];    
 } 
 int mat[MAX][MAX];
int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m))
    {
        int a,b,dis;
        if(n == 0 || m == 0)
            break;
        int i,j;
        for(i = 0 ; i < n;i++)
            for(j = 0 ; j < n; j++)
                mat[i][j] = INF;
        for(i = 0 ; i < m ;i++)
        {
            scanf("%d %d %d",&a,&b,&dis);
            --a,--b;
            if(dis < mat[a][b] || dis < mat[b][a])
            mat[a][b] = mat[b][a] = dis;
        }
        int ans = dijkstra(mat,n,0,n-1);
        printf("%d\n",ans);
    }
 
}

可用 优先队列优化


其他解释:
http://blog.csdn.net/jiahui524/article/details/6636913 
posted on 2012-06-16 03:53 luis 阅读(515) 评论(0)  编辑 收藏 引用 所属分类: 图论*矩阵

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年6月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(3)

随笔分类

随笔档案

文章分类

文章档案

友情链接

搜索

  •  

最新评论

阅读排行榜

评论排行榜