单源最短路径

 单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质。

一.最短路径的最优子结构性质

   该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。

   假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离,那么必定存在另一条从k到s的最短路径P'(k,s),那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。则与P(i,j)是从i到j的最短路径相矛盾。因此该性质得证。

二.Dijkstra算法

   由上述性质可知,如果存在一条从i到j的最短路径(Vi.....Vk,Vj),Vk是Vj前面的一顶点。那么(Vi...Vk)也必定是从i到k的最短路径。为了求出最短路径,Dijkstra就提出了以最短路径长度递增,逐次生成最短路径的算法。譬如对于源顶点V0,首先选择其直接相邻的顶点中长度最短的顶点Vi,那么当前已知可得由V0经过Vi到达与Vi直接相邻的顶点的最短距离dist[j]=min{matrix[V0][j],dist[i]+matrix[i][j]}。根据这种思路,

假设存在G=<V,E>,源顶点为V0,U={V0},dist[i]记录V0到i的最短距离,path[i]记录从V0到i路径上的i前面的一个顶点。

1.从V-U中dist[i]值最小的顶点i,将i加入到U中;

2.更新与i直接相邻顶点的dist值。(dist[j]=min{matrix[V0][j],dist[i]+matrix[i][j]})

3.直到U=V,停止。

代码模版:

template <class Type>
void Dijkstra(int n,int v,Type dist[],int prev[],Type * * c)
{
    bool s[maxint];
    for(int i=1;i<=n;i++)
    {
        dist[i] = c[v][i];
        s[i] = false;
        if(dist[i] == maxint)
            prev[i] = 0;
        else
            prev[i] = v;
    }
    dist[v] = 0;
    s[v] = true;
    for(int i=1;i<n;i++)
    {
        int temp = maxint;
        int u = v;
        for(int j = 1;j<=n;j++)
        {
            if(!(s[j]) && (dist[j] < temp))
            {
                u = j;
                temp = dist[j];
            }
            s[u] = true;//这个是放哪的?
        }
        for(j =1;j<=n;j++)
        {
            if(!(s[j]) && (c[u][j]<maxint))
            {
                Type newdist = dist[u] + c[u][j];
                if(newdist < dist[j])
                {
                    dist[j] = newdist;
                    prev[j] = u;
                }
            }
        }
    }
}

本文转自博客园xingoo的博客,原文链接:单源最短路径,如需转载请自行联系原博主。

时间: 2024-09-23 06:06:50

单源最短路径的相关文章

单源最短路径算法--Dijkstra算法和Bellman-Ford算法

Dijkstra算法 算法流程: (a) 初始化:用起点v到该顶点w的直接边(弧)初始化最短路径,否则设为∞: (b) 从未求得最短路径的终点中选择路径长度最小的终点u:即求得v到u的最短路径: (c) 修改最短路径:计算u的邻接点的最短路径,若(v,-,u)+(u,w)<(v,-,w),则以(v,-,u,w)代替. (d) 重复(b)-(c),直到求得v到其余所有顶点的最短路径. 特点:总是按照从小到大的顺序求得最短路径. 假设一共有N个节点,出发结点为s,需要一个一维数组prev[N]来记录

8万多个结点的图,进行单源最短路径查询,如何使运行的时间减少

问题描述 8万多个路网结点组成的图,进行单源最短路径查询,使用Dijkstra算法的话,运行的时间差不多是1min,换了A*算法后,发现对两个离得近的点查询时,速度很快,但离得比较远的时候,运行的时间超过30min,这是什么原因呢?不是应该A*算法效率比Dijkstra算法要高么..求解 解决方案

[算法系列之三十]Dijkstra单源最短路径算法

单源最短路径问题 给定一个带权有向图 G=(V,E) ,其中每条边的权是一个非负实数.另外,还给定 V 中的一个顶点,称为源.现在我们要计算从源到所有其他各顶点的最短路径长度.这里的长度是指路上各边权之和.这个问题通常称为单源最短路径问题. 前面Bellman-Ford最短路径算法讲了单源最短路径的Bellman-Ford算法(动态规划算法).这里介绍另外一个更常见的算法Dijkstra算法. Dijkstra算法和 最小生成树Prim算法最小生成树算法非常类似,大家可以先熟悉下个算法.两个算法

poj 1502 单源最短路径

一.题目大意 无向图,给出邻接矩阵的下半矩阵,要求源点1,到其他点最短时间(散播整个网络的最短时间). 二.AC code 明显的单源最短路径 但是还是用了Floyd算法撞撞运气,毕竟是无向图,当然可以对Floyd优化,最后也可以A. #include <iostream> #include <stdio.h> #include <cstring> #include <vector> #include <cmath> #include <a

【算法导论】单源最短路径之Bellman-Ford算法

        单源最短路径指的是从一个顶点到其它顶点的具有最小权值的路径.我们之前提到的广度优先搜索算法就是一种无权图上执行的最短路径算法,即在所有的边都具有单位权值的图的一种算法.单源最短路径算法可以解决图中任意顶点间的最短路径.         对于单源最短路径问题,一般有两种经典解法:1.对于有权值为负的图,采用Bellman-Ford算法:2.对于权值全为正的图,常采用Dijkstra算法.本文介绍Bellman-Ford算法,下一篇介绍Dijkstra算法. Bellman-Ford

【算法导论】单源最短路径之Dijkstra算法

        Dijkstra算法解决了有向图上带正权值的单源最短路径问题,其运行时间要比Bellman-Ford算法低,但适用范围比Bellman-Ford算法窄. 迪杰斯特拉提出的按路径长度递增次序来产生源点到各顶点的最短路径的算法思想是:对有n个顶点的有向连通网络G=(V, E),首先从V中取出源点u0放入最短路径顶点集合U中,这时的最短路径网络S=({u0}, {}); 然后从uU和vV-U中找一条代价最小的边(u*, v*)加入到S中去,此时S=({u0, v*}, {(u0,

MapReduce求解物流配送单源最短路径研究

MapReduce求解物流配送单源最短路径研究 钮亮 张宝友 针对物流配送路线优化,提出了将配送路线问题分解成若干可并行操作的子问题的云计算模式.详细论述了基于标色法的MapReduce广度优先算法并行化模型.节点数据结构.算法流程和伪代码程序,并通过将该算法应用于快递公司的实际配送,验证了该算法的可行性. MapReduce求解物流配送单源最短路径研究

单源最短路径算法-Dijkstra

描述: 1)算法思想原理:      Floyd算法是一个经典的动态规划算法.用通俗的语言来描述的话,首先我们的目标是寻找从点i到点j的最短路径.从动态规划的角度看问题,我们需要为这个目标重新做一个诠释(这个诠释正是动态规划最富创造力的精华所在)       从任意节点i到任意节点j的最短路径不外乎2种可能,1是直接从i到j,2是从i经过若干个节点k到j.所以,我们假设Dis(i,j)为节点u到节点v的最短路径的距离,对于每一个节点k,我们检查Dis(i,k) + Dis(k,j) < Dis(

[临时]单源最短路径(Dijkstra算法)

因为没有原创内容,相当于看书笔记,因此本打算发在QQZone,但因为QQ空间日志忽然服务器繁忙,大骂腾讯无奈还是把此日志临时发布在自己的博客上. 参考资料:<计算机算法设计与分析>(第三版). 条件: (1)带权有向图 G = (V, E); 任意边的权 >= 0; 算法: 贪心法.体现在从源节点开始,每次从集合S外"选一个最近的节点"添加到S中,然后对dist数组做更新.   参数说明: T:模板参数,权值类型.(计量长度的数据类型) int n; 图的节点数: i