yuanyuelang

常用链接

统计

最新评论

单源最短路径之Dijkstra算法


单源最短路径，解决的是什么问题呢？
顾名思义，单源说明从一个源出发，出发到哪里呢？不管到哪里我都要求得一个最短的路径。

比较正式的说法：
对于有向图G={V,E},带权，注意Dijkstra算法要求所有的权值非负，
假设我们的源是s，源点要到达的点集合是S，我们每次选择具有最短路径估计的顶点u(u在V-S中，并将u加入到S中，然后此时要对u所有的出边进行处理，怎么处理，我们要最短路径，所以此时要判断s经过u到达V-S中的点会不会比不经过u到达来的小，更新呵呵..

那么怎么写成代码呢？
1.我们需要二维数组graph[][]表示图，用distance[]数组来表示源点V0到其它顶点的最短路径distance[v]，我们还要保存具体路径，我们用path[][]二维bool数组来表示,path[1]就表示源点到顶点V1的路径，path[1][0,n-1]数组里面的元素如果为true表示V0有经过那些顶点到达V1
2.我们还要考虑到顶点是否已经加到S中，用一个flag数组来标志顶点是否已经求的最短路径了。

还要分清是有向图还是无向图，这对于入边和出边在程序处理的时候要注意。 

#define MAXN 100
#define INF 0xfffffff


//注意graph里面的数据，两顶点i指向j有边，长为r，则graph[i][j]=r,其余情况graph为INF，包括i==j

void dijkstra(int graph[MAXN][MAXN],bool path[MAXN][MAXN],int distance[],int n)
{
    int i,j,min,vertex;
    bool flag[MAXN];
    for(i=0;i<n;i++){//初始化
        distance[i]=graph[0][i];
        flag[i]=false;
        for(j=0;j<n;j++) path[i][j]=false;
        if(distance[i]<INF){ //路径必定至少有v0和vi两个顶点
            p[i][0]=true;p[i][i]=true;
        }
    }

    flag[0]=true;
    distance[0]=0;//注意一定要初始化distance[0]
    for(i=1;i<n;i++){
        min=INF;
        for(j=1;j<n;j++)
            if(!flag[j]&&distance[j]<min){//找到最近的点
                min=distance[j];
                vertex=j;
            }
        flag[vertex]=true;
        for(j=1;j<n;j++)
            if(!flag[j]&&graph[vertex][j]+min<distance[j]){//如果可以通过vertex更近的话,更新
                distance[j]=graph[vertex][j]+min;
                for(int k=0;k<n;k++) path[j][k]=path[vertex][k];
                path[j][j]=true;
            }
    }

}


请读者务必自己举个例子，运行看看，这样子才能理解好理解的根深蒂固，还有一定要自己不断的写，自己平常要锻炼，做ACM题目时最好自己再写一遍，不要太依赖模板了哈哈。。

posted on 2009-09-14 21:21 原语饿狼 阅读(612) 评论(0)  编辑 收藏 引用 所属分类: 图论


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