精华内容
下载资源
问答
  • 单源最短路径算法

    千次阅读 2017-10-30 15:37:05
    最短路径问题:如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边上的权值总和达到最小。当然这只是最基础的应用,关于单源最短路径还有很多变体: 1....

    最短路径问题:如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边上的权值总和达到最小。当然这只是最基础的应用,关于单源最短路径还有很多变体:

    1.单源最短路径

    2.单目的地最短路径

    3.单节点对最短路径

    4.所有节点对最短路径

    最短路径定义:

    路径p=<v0, v1, … vk>的权是指组成p的所有边的权值之和


    从u到v的最短路径的权为


    从u到v的最短路径是权的任何路径

    节点V的前驱节点表示为:Vπ

    需要说明的是这里讨论的单源最短路径允许出现负数权值,但是不能图中不能出现权值为负数的环路,因为一旦图中出现了权值为负数的环路那么图中有些节点是不可能有最路径的。例如:图中节点0到节点1权值为1,节点1到节点0权值为-2,那么第一轮从0->1的最短路径为1,但是在节点1的时候发现1->0可以更小也就是-2,下一轮-2+1<1那么节点1的权值被更新为-1,如此循环下去会变成负无穷大。


    常用的单源最短路径的解法有两种:Dijkstra算法和bellman_ford算法。

    松弛操作

    松弛:先测试v到s之间的最短路径是否可以改善,可以则改善。可能很多人会有疑问为什么突然讲了一个松弛操作?这是因为单源最短路径和所有节点对的最短路径都是基于松弛操作来实现的,只不过不同的算法采用了不同的松弛次数和顺序。
    例如下图所示,S-->B的直接距离为8,但是检测S-->A-->B的距离为5;5<8因此进行一次松弛,得到S-->B的距离为5

    实现伪代码:
    w(u,v)表示边u-->v的权值,u.d和v.d分别表示点u和v到源点s的距离
    relax(u,v,w){
        if  v.d>u.d+w(u,v)
    v.d=u.d+w(u,v)
    v.π=v
    }

    bellman_ford算法

    bellman_ford算法可以解决带有负权值的图的单源最短路径,如果图中包含了一个权值为负的环路,则该算法返回false,否则返回true;

    初始化

    初始化很好理解,就是将图G中的所有节点到源结点s的距离设置为表示不可达,而且将所有节点的父节点设置为null,当然s除外

    init(G,s){
        foreach  vertex u∈G.V
                    u.d=∞
                    u.π=null
        s.d=0;
    }

    核心思想

    对每一条边都进行V次松弛操作。或者换一种说法:每次都将所有的边进行松弛,一共持续V次。

    这里可以做一个简单的证明为什么这样操作可以得到最短路径;证明之前大家需要先知道一个定理:最短路径中不可能包含环路,如果环路为负那么最终得不到最短路,该算法也会返回false,如果环路为正,那么去掉这个环路一定可以比当前方案更优,而如果环路为0,那么可以直接不用这个环路。有了这个定理,我们可以很简单的推出在含有V个节点的图中,u到v的最短路径最多可以包含V-1条边。我们的算法是每次都对所有的边进行松弛,那么经过V-1次的松弛之后一定可以得到最短路径,当然如果不存在负值环路的话,当松弛的次数大于V-1的时候,各个节点到源结点s的最短距离不会再改变,因为在V-1次的时候已经达到最优。

    算法伪代码:

    G是图形,w是所有边的权值集合,s是源结点,

    Bellman_Ford(G,w,s){
            init(G,s);
    for i=1 to |G.V| - 1
      for each edge(u,v)∈G.E
    relax(u,v,w)
    for each edge(u,v)∈G.E
    if v.d>u.d+w(u,v)//只有存在负值环路的时候该条件才会被满足
    return false
    return true
    }

    实例分析

    举一个实例手动模拟一下上面的算法,下图中的a是初始化的状态,b是第1次对所有边进行松弛的结果,c是第2次对所有边进行松弛的结果,d是第3次对所有边进行松弛的结果,e是第4次对所有边进行松弛的结果。

    第一次松弛的时候可以看到检测t-->x,y-->x,y-->z等都是∞加上某个数字,属于不可改善的情况,只有与s直接相连的t和y是可以改善的,因此第一次松弛只能改善t和y到s的距离。后面的几次都是这样分析这里不再啰嗦。


    实现代码(仅作参考)

    #include<iostream>
    #include<climits>
    const int M=100;
    using namespace std;
    struct vertex{
    	int smallCost;
    	int father;
    }; 
    struct edge{
    	int start;
    	int end;
    	int cost;
    };
    vertex V[M];
    edge arr[M];
    void init(int v,int s){//v个节点,对v进行初始化,s为起点 
    	for(int i=1;i<=v;i++){
    		V[i].smallCost=INT_MAX;
    		V[i].father=-1;
    	}
    	V[s].smallCost=0;	
    }
    bool bell_fold(int v,int e,int s){//时间复杂度为:O(VE) 
    	init(v,s);
    	for(int i=1;i<=v-1;i++){
    		for(int j=1;j<=e;j++){
    				int x=arr[j].start;
    				int y=arr[j].end;
    				int z=arr[j].cost;
    				if(V[x].smallCost!=INT_MAX&&V[y].smallCost>V[x].smallCost+z){
    					V[y].smallCost=V[x].smallCost+z;
    					V[y].father=x;
    				}
    		}
    	}
    	for(int j=1;j<=e;j++){
    		int x=arr[j].start;
    		int y=arr[j].end;
    		int z=arr[j].cost;
    		if(V[x].smallCost!=INT_MAX&&V[y].smallCost>V[x].smallCost+z)
    			return false;			
    	}
    	return true;
    }
    void printPath(int src,int des){
    	if(des==src)
    		cout<<des;
    	else{
    		printPath(src,V[des].father);
    		cout<<"-->"<<des;
    	}
    	
    }
    int main(){
    	int v,e,s;//v个顶点e条边 s为起始点
    	cin>>v>>e>>s;
    	for(int i=1;i<=e;i++)
    		cin>>arr[i].start>>arr[i].end>>arr[i].cost;
    	bell_fold(v,e,s);
    	for(int i=1;i<=v;i++){
    		cout<<"from "<<s<<" to "<<i<<" smallest cost:"<<V[i].smallCost<<".path:";
    		printPath(s,i);
    		cout<<endl;	
    	}
    	
    	return 0;
    }
    /* 
    5 10 1
    1 2 6
    1 5 7
    2 5 8
    2 3 5
    3 2 -2
    4 1 2
    4 3 7
    2 4 -4
    5 3 -3
    5 4 9
    */

    时间复杂度

            该算法的时间复杂度很好分析,对每一条边都进行V次的松弛,因此该算法的时间复杂度为O(VE),对于稀疏图而言的话效率还算不错,但是对于稠密图(E≈V^2),效率不是很高,因为稠密图的时候O(VE)≈O(V^3)。整体而言效率并不是特别高。一般而言,算法效率不高是因为大量的重复操作,下面我们来分析一下都有哪些重复操作。我们在进行实例分析的时候会发现,如果有很多个节点,而且有很多条边的话,在前几次的松弛中会做很多无用操作,因为都是∞不能松弛,而在最后几次松弛中前面已经有很多节点是达到了最优,所以也不能进行松弛,这些无用的重复操作是造成算法效率不高的主要原因。

    dijkstra算法

            经过分析我们发现bellman_ford算法存在大量的重复无用操作,这里我们介绍一种贪心算法,可以有效的减少这种无用重复操作,但是有一个前提是所有边的权值必须是正的,不可以解决权值为负数的图的最短路径。

    核心思想

    以源结点s为起始点,一层一层的扩展,直到找到终点。

    算法步骤:

    引入一个辅助数组d。它的每一个分量d[i]表示目前为止找到的从源点v0到终点vi 的最短路径的长度。

    初始状态:
    若从源点v0到顶点vi有边,则d[i]为该边上的权值;
    若从源点v0到顶点vi 没有边,则d[i]为+∞。
    把源点v0加入集合S。

    算法步骤:
    1.找出V- S 中距离源点最近的顶点k,将其加入S:
      d[k] ← min{d[i]}; 
             S ← S ∪ { k };
     2.修改V- S 中,与刚刚加入的顶点k相邻接的顶点的对应属性d:  
            for each i ∈ V- S ,  and <k,i>∈E 
    d[i] ← min{ d[i], d[k] + w(k,i) }; 
    3. 判断:  若S = V, 则算法结束,否则转1

    实例推导

    下图取自“华山大师兄”的博客,但是动态图看起来简洁明了,自己懒得做。


    算法步骤是指导纲要,具体实施还是要看oIer的水平,

    代码实现:

    变量及其说明,如果不光是求出某两个节点之间的最短路径,要求出最短路径的具体路径,就需要增加一个属性保存前驱节点,因此我将他们直接封装为一个struct,node表示某个节点的信息,father是该节点的直接前驱节点,cost表示该节点到源结点的最短路径值。另外,使用领接链表的形式存储图,因为使用指针太麻烦了,而且容易出错,关键是还需要要自己去分配内存,因此直接使用了vector数组来模拟,以减少实现难度。当然这里同样可以使用list数组模拟,但是那样不能像二维数组一样直接使用双下标取值,要使用迭代器也是比较麻烦的。

    struct node{//顶点信息 
    	int father;//该节点的直接父节点 
    	int cost;//该节点到源结点的最短权值 
    }; 
    struct edge{//所有边都会加入到数组vector中去,数组下标为该边的起点 
    	int dest;//边的结束点的下标 
    	int cost;
    };
    node vertex[M];
    bool isVisited[M]={0};//表示某个节点是不是被访问过 
    vector<edge> graph[M];//挂链表的形式保存图,因为要修改某个节点领接节点的值,所以必须保存图
    初始化

    void init(int v,int s){//v个节点,对所有节点初始化,s为起点 
    	for(int i=1;i<=v;i++){
    		vertex[i].cost=INT_MAX;//所有节点的权值都是∞ 
    		vertex[i].father=i;//父节点都是节点本身 
    	}
    	vertex[s].cost=0;//源结点的权值为0 
    }
    dijkstra算法框架

    void dijkstra(int v,int e,int s){//时间复杂度为:O(V^2+E) 
    	init(v,s);//初始化 
    	for(int i=1;i<=v;i++){//一共有V个节点,每次取出一个节点,因此一共需要执行V次 
    		int u=getMin(v);//取得离源结点最近的节点 
    		relax(u);//松弛所有与源结点相邻的节点 
    	}
    }

    获取最小值

    取得最小值有两种操作方式,第一种是O(n)复杂度的遍历,第二种是O(1)时间的小根堆,不过小根堆实现比较难,但是删除和建立时间复杂度为lgN比直接遍历效率高;本来最开始准备直接使用stl中的priority_queue,后面发现加入到优先级队列里面的元素的值并不能进行改变,写小根堆又太麻烦了就直接遍历了,如果需要深入学习写高效率的建议使用堆来实现。

    int getMin(int v){//获取没有访问过的最小节点 
    	int res=INT_MAX;
    	int index=-1;
    	for(int i=1;i<=v;i++){
    		if((isVisited[i]==0)&&(res>=vertex[i].cost)){
    			res=vertex[i].cost;
    			index=i;
    		}
    	}
    	isVisited[index]=1;
    	return index;
    }

    路径打印

    只要知道每个节点的直接前驱节点,那么一定可以得到完整的路径,因为最短路径具有最优子结构的性质。(最优子结构就是如果结果最优,那么过程中得到的过度结果也一定最优)关于最优子结构其实不难证明,假设A------->D的最优结果k是A-->C--->D,并且A-->C的距离为x,C-->D的距离为y,也就是说k=x+y;现在假设A-->C的最优结果是x1而不是x,那么就意味着x1<x,如果上式成立,那么x1+y<x+y一定成立,也就是说A--------->D的最优结果不是k这与原假设矛盾。因此如果A------D最优结果途径C那么A----->C也一定最优。所以我们只需要知道每个节点的前驱节点就一定可以打印一条最短路径出来。

    void printPath(int startPoint,int destination){
    	if(destination==startPoint)
    		cout<<destination;
    	else{
    		printPath(startPoint,vertex[destination].father);
    		cout<<"-->"<<destination;
    	}
    }
    完整代码

    #include<iostream>
    #include<climits>
    #include<vector>
    const int M=100;
    using namespace std;
    struct node{//顶点信息 
    	int father;//该节点的直接父节点 
    	int cost;//该节点到源结点的最短权值 
    }; 
    struct edge{//所有边都会加入到数组中去,数组下标为该边的起点 
    	int dest;//边的结束点的下标 
    	int cost;
    };
    node vertex[M];
    bool isVisited[M]={0};//表示某个节点是不是被访问过 
    vector<edge> graph[M];//挂链表的形式保存图,因为要修改某个节点领接节点的值,所以必须保存图 
    void printVertex(int v){//输出顶点到源结点的最小距离 
    	for(int i=1;i<=v;i++)
    	cout<<i<<":"<<vertex[i].cost<<"   "<<vertex[i].father<<endl;
    } 
    void init(int v,int s){//v个节点,对所有节点初始化,s为起点 
    	for(int i=1;i<=v;i++){
    		vertex[i].cost=INT_MAX;//所有节点的权值都是∞ 
    		vertex[i].father=i;//父节点都是节点本身 
    	}
    	vertex[s].cost=0;//源结点的权值为0 
    }
    int getMin(int v){//获取没有访问过的最小节点 
    	int res=INT_MAX;
    	int index=-1;
    	for(int i=1;i<=v;i++){
    		if((isVisited[i]==0)&&(res>=vertex[i].cost)){
    			res=vertex[i].cost;
    			index=i;
    		}
    	}
    	isVisited[index]=1;
    	return index;
    }
    void relax(int u){//对和u相连接的所有节点进行松弛 
    	int len=graph[u].size();
    	for(int i=0;i<len;i++){
    		int des=(graph[u][i]).dest;
    		if((vertex[u].cost!=INT_MAX)&&(vertex[des].cost>vertex[u].cost+(graph[u][i]).cost)){
    			vertex[des].cost=vertex[u].cost+(graph[u][i]).cost;
    			vertex[des].father=u;
    		}
    	}
    }
    void dijkstra(int v,int e,int s){//时间复杂度为:O(V^2+E) 
    	init(v,s);//初始化 
    	for(int i=1;i<=v;i++){//一共有V个节点,每次取出一个节点,因此一共需要执行V次 
    		int u=getMin(v);//取得离源结点最近的节点 
    		relax(u);//松弛所有与源结点相邻的节点 
    	}
    }
    void printPath(int startPoint,int destination){
    	if(destination==startPoint)
    		cout<<destination;
    	else{
    		printPath(startPoint,vertex[destination].father);
    		cout<<"-->"<<destination;
    	}
    }
    
    void printRoad(int v,int s){
    	for(int i=1;i<=v;i++){
    		cout<<"from "<<s<<" to "<<i<<" smallest cost:"<<vertex[i].cost<<".path:";
    		printPath(s,i);
    		cout<<endl;	
    	}
    }
    int main(){
    	int v,e,s;//v个顶点e条边 s为起始点
    	cin>>v>>e>>s;
    	int a,b,c;//a到b的花费为c 
    	edge temp;
    	for(int i=1;i<=e;i++){
    		cin>>a>>b>>c;
    		temp.dest=b;
    		temp.cost=c;
    		graph[a].push_back(temp);
    	}
    	dijkstra(v,e,s);
    	printRoad(v,s);
    }
    /* 
    5 10 1
    1 2 10
    1 5 5
    2 5 2
    2 3 1
    3 4 4
    4 1 7
    4 3 6
    5 2 3
    5 3 9
    5 4 2
    */
    

    时间复杂度

    使用便利的方式来找到最小值的效率偏低,整个算法时间复杂度为O(V^2),如果使用小根堆算法效率可以达到O(VlgV),但是高效率跟随者实现难度,因此oIer们一定要在时间,实现难度,效率,得分之间进行平衡。该算法相比于bellman_ford算法减少了不必要的重复操作,但是必须熟记,该算法只能用于权值为正数的情况。



    展开全文
  • 算法一:A*寻路初探 From GameDev.net 译者序:很久以前就知道了A*算法,但是从未认真读过相关的文章,也没有看过代码,只是脑子里有个模糊的概念。这次决定从头开始,研究一下这个被人推崇备至的简单方法,作为学习...

    算法一:A*寻路初探
    From GameDev.net


    译者序:很久以前就知道了A*算法,但是从未认真读过相关的文章,也没有看过代码,只是脑子里有个模糊的概念。这次决定从头开始,研究一下这个被人推崇备至的简单方法,作为学习人工智能的开始。
    这 篇文章非常知名,国内应该有不少人翻译过它,我没有查找,觉得翻译本身也是对自身英文水平的锻炼。经过努力,终于完成了文档,也明白的A*算法的原理。毫 无疑问,作者用形象的描述,简洁诙谐的语言由浅入深的讲述了这一神奇的算法,相信每个读过的人都会对此有所认识(如果没有,那就是偶的翻译太差了-- b)。
    原文链接:http://www.gamedev.net/reference/articles/article2003.asp
    以下是翻译的正文。(由于本人使用ultraedit编辑,所以没有对原文中的各种链接加以处理(除了图表),也是为了避免未经许可链接的嫌疑,有兴趣的读者可以参考原文。

    会者不难,A*(念作A星)算法对初学者来说的确有些难度。

    这篇文章并不试图对这个话题作权威的陈述。取而代之的是,它只是描述算法的原理,使你可以在进一步的阅读中理解其他相关的资料。

    最后,这篇文章没有程序细节。你尽可以用任意的计算机程序语言实现它。如你所愿,我在文章的末尾包含了一个指向例子程序的链接。 压缩包包括C++和Blitz Basic两个语言的版本,如果你只是想看看它的运行效果,里面还包含了可执行文件。

    我们正在提高自己。让我们从头开始。。。

    序:搜索区域

    假设有人想从A点移动到一墙之隔的B点,如下图,绿色的是起点A,红色是终点B,蓝色方块是中间的墙。

     
    [图1]

    你 首先注意到,搜索区域被我们划分成了方形网格。像这样,简化搜索区域,是寻路的第一步。这一方法把搜索区域简化成了一个二维数组。数组的每一个元素是网格 的一个方块,方块被标记为可通过的和不可通过的。路径被描述为从A到B我们经过的方块的集合。一旦路径被找到,我们的人就从一个方格的中心走向另一个,直 到到达目的地。

    这些中点被称为“节点”。当你阅读其他的寻路资料时,你将经常会看到人们讨论节点。为什么不把他们描述为方格呢?因为有可 能你的路径被分割成其他不是方格的结构。他们完全可以是矩形,六角形,或者其他任意形状。节点能够被放置在形状的任意位置-可以在中心,或者沿着边界,或 其他什么地方。我们使用这种系统,无论如何,因为它是最简单的。

    开始搜索

    正如我们处理上图网格的方法,一旦搜索区域被转化为容易处理的节点,下一步就是去引导一次找到最短路径的搜索。在A*寻路算法中,我们通过从点A开始,检查相邻方格的方式,向外扩展直到找到目标。

    我们做如下操作开始搜索:


       1,从点A开始,并且把它作为待处理点存入一个“开启列表”。开启列表就像一张购物清单。尽管现在列表里只有一个元素,但以后就会多起来。你的路径可能会通过它包含的方格,也可能不会。基本上,这是一个待检查方格的列表。
       2,寻找起点周围所有可到达或者可通过的方格,跳过有墙,水,或其他无法通过地形的方格。也把他们加入开启列表。为所有这些方格保存点A作为“父方格”。当我们想描述路径的时候,父方格的资料是十分重要的。后面会解释它的具体用途。
       3,从开启列表中删除点A,把它加入到一个“关闭列表”,列表中保存所有不需要再次检查的方格。

    在这一点,你应该形成如图的结构。在图中,暗绿色方格是你起始方格的中心。它被用浅蓝色描边,以表示它被加入到关闭列表中了。所有的相邻格现在都在开启列表中,它们被用浅绿色描边。每个方格都有一个灰色指针反指他们的父方格,也就是开始的方格。


    [图2]

    接着,我们选择开启列表中的临近方格,大致重复前面的过程,如下。但是,哪个方格是我们要选择的呢?是那个F值最低的。

    路径评分

    选择路径中经过哪个方格的关键是下面这个等式:

    F = G + H

    这里:
        * G = 从起点A,沿着产生的路径,移动到网格上指定方格的移动耗费。
        * H = 从网格上那个方格移动到终点B的预估移动耗费。这经常被称为启发式的,可能会让你有点迷惑。这样叫的原因是因为它只是个猜测。我们没办法事先知道路径的长 度,因为路上可能存在各种障碍(墙,水,等等)。虽然本文只提供了一种计算H的方法,但是你可以在网上找到很多其他的方法。

    我们的路径是通过反复遍历开启列表并且选择具有最低F值的方格来生成的。文章将对这个过程做更详细的描述。首先,我们更深入的看看如何计算这个方程。

    正 如上面所说,G表示沿路径从起点到当前点的移动耗费。在这个例子里,我们令水平或者垂直移动的耗费为10,对角线方向耗费为14。我们取这些值是因为沿对 角线的距离是沿水平或垂直移动耗费的的根号2(别怕),或者约1.414倍。为了简化,我们用10和14近似。比例基本正确,同时我们避免了求根运算和小 数。这不是只因为我们怕麻烦或者不喜欢数学。使用这样的整数对计算机来说也更快捷。你不就就会发现,如果你不使用这些简化方法,寻路会变得很慢。

    既然我们在计算沿特定路径通往某个方格的G值,求值的方法就是取它父节点的G值,然后依照它相对父节点是对角线方向或者直角方向(非对角线),分别增加14和10。例子中这个方法的需求会变得更多,因为我们从起点方格以外获取了不止一个方格。

    H 值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法,它计算从当前格到目的格之间水平和垂直的方格的数量总和,忽略对角线方向。然后把结果乘以 10。这被成为曼哈顿方法是因为它看起来像计算城市中从一个地方到另外一个地方的街区数,在那里你不能沿对角线方向穿过街区。很重要的一点,我们忽略了一 切障碍物。这是对剩余距离的一个估算,而非实际值,这也是这一方法被称为启发式的原因。想知道更多?你可以在这里找到方程和额外的注解。

    F的值是G和H的和。第一步搜索的结果可以在下面的图表中看到。F,G和H的评分被写在每个方格里。正如在紧挨起始格右侧的方格所表示的,F被打印在左上角,G在左下角,H则在右下角。


    [图3]

    现在我们来看看这些方格。写字母的方格里,G = 10。这是因为它只在水平方向偏离起始格一个格距。紧邻起始格的上方,下方和左边的方格的G值都等于10。对角线方向的G值是14。

    H 值通过求解到红色目标格的曼哈顿距离得到,其中只在水平和垂直方向移动,并且忽略中间的墙。用这种方法,起点右侧紧邻的方格离红色方格有3格距离,H值就 是30。这块方格上方的方格有4格距离(记住,只能在水平和垂直方向移动),H值是40。你大致应该知道如何计算其他方格的H值了~。

    每个格子的F值,还是简单的由G和H相加得到

    继续搜索

    为了继续搜索,我们简单的从开启列表中选择F值最低的方格。然后,对选中的方格做如下处理:

       4,把它从开启列表中删除,然后添加到关闭列表中。
       5,检查所有相邻格子。跳过那些已经在关闭列表中的或者不可通过的(有墙,水的地形,或者其他无法通过的地形),把他们添加进开启列表,如果他们还不在里面的话。把选中的方格作为新的方格的父节点。
       6,如果某个相邻格已经在开启列表里了,检查现在的这条路径是否更好。换句话说,检查如果我们用新的路径到达它的话,G值是否会更低一些。如果不是,那就什么都不做。
          另一方面,如果新的G值更低,那就把相邻方格的父节点改为目前选中的方格(在上面的图表中,把箭头的方向改为指向这个方格)。最后,重新计算F和G的值。如果这看起来不够清晰,你可以看下面的图示。

    好了,让我们看看它是怎么运作的。我们最初的9格方格中,在起点被切换到关闭列表中后,还剩8格留在开启列表中。这里面,F值最低的那个是起始格右侧紧邻的格子,它的F值是40。因此我们选择这一格作为下一个要处理的方格。在紧随的图中,它被用蓝色突出显示。


    [图4]

    首先,我们把它从开启列表中取出,放入关闭列表(这就是他被蓝色突出显示的原因)。然后我们检查相邻的格子。哦,右侧的格子是墙,所以我们略过。左侧的格子是起始格。它在关闭列表里,所以我们也跳过它。

    其 他4格已经在开启列表里了,于是我们检查G值来判定,如果通过这一格到达那里,路径是否更好。我们来看选中格子下面的方格。它的G值是14。如果我们从当 前格移动到那里,G值就会等于20(到达当前格的G值是10,移动到上面的格子将使得G值增加10)。因为G值20大于14,所以这不是更好的路径。如果 你看图,就能理解。与其通过先水平移动一格,再垂直移动一格,还不如直接沿对角线方向移动一格来得简单。

    当我们对已经存在于开启列表中的4个临近格重复这一过程的时候,我们发现没有一条路径可以通过使用当前格子得到改善,所以我们不做任何改变。既然我们已经检查过了所有邻近格,那么就可以移动到下一格了。

    于 是我们检索开启列表,现在里面只有7格了,我们仍然选择其中F值最低的。有趣的是,这次,有两个格子的数值都是54。我们如何选择?这并不麻烦。从速度上 考虑,选择最后添加进列表的格子会更快捷。这种导致了寻路过程中,在靠近目标的时候,优先使用新找到的格子的偏好。但这无关紧要。(对相同数值的不同对 待,导致不同版本的A*算法找到等长的不同路径。)

    那我们就选择起始格右下方的格子,如图。


    [图5]

    这 次,当我们检查相邻格的时候,发现右侧是墙,于是略过。上面一格也被略过。我们也略过了墙下面的格子。为什么呢?因为你不能在不穿越墙角的情况下直接到达 那个格子。你的确需要先往下走然后到达那一格,按部就班的走过那个拐角。(注解:穿越拐角的规则是可选的。它取决于你的节点是如何放置的。)

    这 样一来,就剩下了其他5格。当前格下面的另外两个格子目前不在开启列表中,于是我们添加他们,并且把当前格指定为他们的父节点。其余3格,两个已经在开启 列表中(起始格,和当前格上方的格子,在表格中蓝色高亮显示),于是我们略过它们。最后一格,在当前格的左侧,将被检查通过这条路径,G值是否更低。不必 担心,我们已经准备好检查开启列表中的下一格了。

    我们重复这个过程,只到目标格被添加进开启列表,就如在下面的图中所看到的。


    [图6]

    注 意,起始格下方格子的父节点已经和前面不同的。之前它的G值是28,并且指向右上方的格子。现在它的G值是20,指向它上方的格子。这在寻路过程中的某处 发生,当应用新路径时,G值经过检查变得低了-于是父节点被重新指定,G和F值被重新计算。尽管这一变化在这个例子中并不重要,在很多场合,这种变化会导 致寻路结果的巨大变化。

    那么,我们怎么确定这条路径呢?很简单,从红色的目标格开始,按箭头的方向朝父节点移动。这最终会引导你回到起始格,这就是你的路径!看起来应该像图中那样。从起始格A移动到目标格B只是简单的从每个格子(节点)的中点沿路径移动到下一个,直到你到达目标点。就这么简单。


    [图7]

    A*方法总结

    好,现在你已经看完了整个说明,让我们把每一步的操作写在一起:

       1,把起始格添加到开启列表。
       2,重复如下的工作:
          a) 寻找开启列表中F值最低的格子。我们称它为当前格。
          b) 把它切换到关闭列表。
          c) 对相邻的8格中的每一个?
              * 如果它不可通过或者已经在关闭列表中,略过它。反之如下。
              * 如果它不在开启列表中,把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
              * 如果它已经在开启列表中,用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序,改变之后你可能需要重新对开启列表排序。

          d) 停止,当你
              * 把目标格添加进了开启列表,这时候路径被找到,或者
              * 没有找到目标格,开启列表已经空了。这时候,路径不存在。
       3.保存路径。从目标格开始,沿着每一格的父节点移动直到回到起始格。这就是你的路径。

    题外话

    离 题一下,见谅,值得一提的是,当你在网上或者相关论坛看到关于A*的不同的探讨,你有时会看到一些被当作A*算法的代码而实际上他们不是。要使用A*,你 必须包含上面讨论的所有元素--特定的开启和关闭列表,用F,G和H作路径评价。有很多其他的寻路算法,但他们并不是A*,A*被认为是他们当中最好的。 Bryan Stout在这篇文章后面的参考文档中论述了一部分,包括他们的一些优点和缺点。有时候特定的场合其他算法会更好,但你必须很明确你在作什么。好了,够多 的了。回到文章。

    实现的注解

    现在你已经明白了基本原理,写你的程序的时候还得考虑一些额外的东西。下面这些材料中的一些引用了我用C++和Blitz Basic写的程序,但对其他语言写的代码同样有效。

    1, 维护开启列表:这是A*寻路算法最重要的组成部分。每次你访问开启列表,你都需要寻找F值最低的方格。有几种不同的方法实现这一点。你可以把路径元素随意 保存,当需要寻找F值最低的元素的时候,遍历开启列表。这很简单,但是太慢了,尤其是对长路径来说。这可以通过维护一格排好序的列表来改善,每次寻找F值 最低的方格只需要选取列表的首元素。当我自己实现的时候,这种方法是我的首选。

    在小地图。这种方法工作的很好,但它并不是最快的解决方 案。更苛求速度的A*程序员使用叫做“binary heap”的方法,这也是我在代码中使用的方法。凭我的经验,这种方法在大多数场合会快2~3倍,并且在长路经上速度呈几何级数提升(10倍以上速度)。 如果你想了解更多关于binary heap的内容,查阅我的文章,Using Binary Heaps in A* Pathfinding。

    2, 其他单位:如果你恰好看了我的例子代码,你会发现它完全忽略了其他单位。我的寻路者事实上可以相互穿越。取决于具体的游戏,这也许可以,也许不行。如果你 打算考虑其他单位,希望他们能互相绕过,我建议在寻路算法中忽略其他单位,写一些新的代码作碰撞检测。当碰撞发生,你可以生成一条新路径或者使用一些标准 的移动规则(比如总是向右,等等)直到路上没有了障碍,然后再生成新路径。为什么在最初的路径计算中不考虑其他单位呢?那是因为其他单位会移动,当你到达 他们原来的位置的时候,他们可能已经离开了。这有可能会导致奇怪的结果,一个单位突然转向,躲避一个已经不在那里的单位,并且会撞到计算完路径后,冲进它 的路径中的单位。

    然而,在寻路算法中忽略其他对象,意味着你必须编写单独的碰撞检测代码。这因游戏而异,所以我把这个决定权留给你。参考文献列表中,Bryan Stout的文章值得研究,里面有一些可能的解决方案(像鲁棒追踪,等等)。

    3, 一些速度方面的提示:当你开发你自己的A*程序,或者改写我的,你会发现寻路占据了大量的CPU时间,尤其是在大地图上有大量对象在寻路的时候。如果你阅 读过网上的其他材料,你会明白,即使是开发了星际争霸或帝国时代的专家,这也无可奈何。如果你觉得寻路太过缓慢,这里有一些建议也许有效:

        * 使用更小的地图或者更少的寻路者。
        * 不要同时给多个对象寻路。取而代之的是把他们加入一个队列,把寻路过程分散在几个游戏周期中。如果你的游戏以40周期每秒的速度运行,没人能察觉。但是他们会发觉游戏速度突然变慢,当大量寻路者计算自己路径的时候。
        * 尽量使用更大的地图网格。这降低了寻路中搜索的总网格数。如果你有志气,你可以设计两个或者更多寻路系统以便使用在不同场合,取决于路径的长度。这也正是 专业人士的做法,用大的区域计算长的路径,然后在接近目标的时候切换到使用小格子/区域的精细寻路。如果你对这个观点感兴趣,查阅我的文章Two- Tiered A* Pathfinding。
        * 使用路径点系统计算长路径,或者预先计算好路径并加入到游戏中。
        * 预处理你的地图,表明地图中哪些区域是不可到达的。我把这些区域称作“孤岛”。事实上,他们可以是岛屿或其他被墙壁包围等无法到达的任意区域。A*的下限 是,当你告诉它要寻找通往那些区域的路径时,它会搜索整个地图,直到所有可到达的方格/节点都被通过开启列表和关闭列表的计算。这会浪费大量的CPU时 间。可以通过预先确定这些区域(比如通过flood-fill或类似的方法)来避免这种情况的发生,用某些种类的数组记录这些信息,在开始寻路前检查它。 在我Blitz版本的代码中,我建立了一个地图预处理器来作这个工作。它也标明了寻路算法可以忽略的死端,这进一步提高了寻路速度。

    4, 不同的地形损耗:在这个教程和我附带的程序中,地形只有两种-可通过的和不可通过的。但是你可能会需要一些可通过的地形,但是移动耗费更高-沼泽,小山, 地牢的楼梯,等等。这些都是可通过但是比平坦的开阔地移动耗费更高的地形。类似的,道路应该比自然地形移动耗费更低。

    这个问题很容易解 决,只要在计算任何地形的G值的时候增加地形损耗就可以了。简单的给它增加一些额外的损耗就可以了。由于A*算法已经按照寻找最低耗费的路径来设计,所以 很容易处理这种情况。在我提供的这个简单的例子里,地形只有可通过和不可通过两种,A*会找到最短,最直接的路径。但是在地形耗费不同的场合,耗费最低的 路径也许会包含很长的移动距离-就像沿着路绕过沼泽而不是直接穿过它。

    一种需额外考虑的情况是被专家称之为“influence mapping”的东西(暂译为影响映射图)。就像上面描述的不同地形耗费一样,你可以创建一格额外的分数系统,并把它应用到寻路的AI中。假设你有一张 有大批寻路者的地图,他们都要通过某个山区。每次电脑生成一条通过那个关口的路径,它就会变得更拥挤。如果你愿意,你可以创建一个影响映射图对有大量屠杀 事件的格子施以不利影响。这会让计算机更倾向安全些的路径,并且帮助它避免总是仅仅因为路径短(但可能更危险)而持续把队伍和寻路者送到某一特定路径。

    5,处理未知区域:你是否玩过这样的PC游戏,电脑总是知道哪条路是正确的,即使它还没有侦察过地图?对于游戏,寻路太好会显得不真实。幸运的是,这是一格可以轻易解决的问题。

    答 案就是为每个不同的玩家和电脑(每个玩家,而不是每个单位--那样的话会耗费大量的内存)创建一个独立的“knownWalkability”数组,每个 数组包含玩家已经探索过的区域,以及被当作可通过区域的其他区域,直到被证实。用这种方法,单位会在路的死端徘徊并且导致错误的选择直到他们在周围找到 路。一旦地图被探索了,寻路就像往常那样进行。

    6,平滑路径:尽管A*提供了最短,最低代价的路径,它无法自动提供看起来平滑的路径。看一下我们的例子最终形成的路径(在图7)。最初的一步是起始格的右下方,如果这一步是直接往下的话,路径不是会更平滑一些吗?

    有 几种方法来解决这个问题。当计算路径的时候可以对改变方向的格子施加不利影响,对G值增加额外的数值。也可以换种方法,你可以在路径计算完之后沿着它跑一 遍,找那些用相邻格替换会让路径看起来更平滑的地方。想知道完整的结果,查看Toward More Realistic Pathfinding,一篇(免费,但是需要注册)Marco Pinter发表在Gamasutra.com的文章

    7,非方形搜索区 域:在我们的例子里,我们使用简单的2D方形图。你可以不使用这种方式。你可以使用不规则形状的区域。想想冒险棋的游戏,和游戏中那些国家。你可以设计一 个像那样的寻路关卡。为此,你可能需要建立一个国家相邻关系的表格,和从一个国家移动到另一个的G值。你也需要估算H值的方法。其他的事情就和例子中完全 一样了。当你需要向开启列表中添加新元素的时候,不需使用相邻的格子,取而代之的是从表格中寻找相邻的国家。

    类似的,你可以为一张确定的 地形图创建路径点系统,路径点一般是路上,或者地牢通道的转折点。作为游戏设计者,你可以预设这些路径点。两个路径点被认为是相邻的如果他们之间的直线上 没有障碍的话。在冒险棋的例子里,你可以保存这些相邻信息在某个表格里,当需要在开启列表中添加元素的时候使用它。然后你就可以记录关联的G值(可能使用 两点间的直线距离),H值(可以使用到目标点的直线距离),其他都按原先的做就可以了。

    另一个在非方形区域搜索RPG地图的例子,查看我的文章Two-Tiered A* Pathfinding。

    进一步的阅读

    好,现在你对一些进一步的观点有了初步认识。这时,我建议你研究我的源代码。包里面包含两个版本,一个是用C++写的,另一个用Blitz Basic。顺便说一句,两个版本都注释详尽,容易阅读,这里是链接。

        * 例子代码:A* Pathfinder (2D) Version 1.71

    如 果你既不用C++也不用Blitz Basic,在C++版本里有两个小的可执行文件。Blitz Basic可以在从Blitz Basic网站免费下载的litz Basic 3D(不是Blitz Plus)演示版上运行。Ben O&#39;Neill提供一个联机演示可以在这里找到。

    你也该看看以下的网页。读了这篇教程后,他们应该变得容易理解多了。

        * Amit的 A* 页面:这是由Amit Patel制作,被广泛引用的页面,如果你没有事先读这篇文章,可能会有点难以理解。值得一看。尤其要看Amit关于这个问题的自己的看法。
        * Smart Moves:智能寻路:Bryan Stout发表在Gamasutra.com的这篇文章需要注册才能阅读。注册是免费的而且比起这篇文章和网站的其他资源,是非常物有所值的。Bryan 用Delphi写的程序帮助我学习A*,也是我的A*代码的灵感之源。它还描述了A*的几种变化。
        * 地形分析:这是一格高阶,但是有趣的话题,Dave Pottinge撰写,Ensemble Studios的专家。这家伙参与了帝国时代和君王时代的开发。别指望看懂这里所有的东西,但是这是篇有趣的文章也许会让你产生自己的想法。它包含一些对 mip-mapping,influence mapping以及其他一些高级AI/寻路观点。对"flood filling"的讨论使我有了我自己的“死端”和“孤岛”的代码的灵感,这些包含在我Blitz版本的代码中。

    其他一些值得一看的网站:

        * aiGuru: Pathfinding
        * Game AI Resource: Pathfinding
        * GameDev.net: Pathfinding

     

    展开全文
  • 图论之最短路径算法

    2020-12-30 16:14:16
    图论之最短路径算法,朴素Dijkstra算法,小根堆优化的Dijkstra算法,BellMan-Ford算法,SPFA算法以及如何判断负环,多源最短路问题的Floyd算法

    在这里插入图片描述

    Dijkstra 算法

    迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。
    是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。

    算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止

    朴素Dijkstra算法

    https://www.acwing.com/problem/content/851/

    在这里插入图片描述

    变量解释

    变量名含义
    int g[N][N]g[i][j] i->j 的距离
    int dis[N]dis[i] 1->i 的最短距离
    bool vis[N]vis[i] 当前1->i 的最短距离是否确定
    int n,mn个点,m条边

    算法流程

    1. 初始化最短距离。起点到自己的最短距离为0,到其他点的距离为INF(0x3f3f3f3f)
    2. 找距离起点最近的点。在没有确定最短距离的点中,找到距离起点距离最近的一个点
    3. 标记。将2找到的最近的点标记为已经确定最短路径的点
    4. 松弛。用2找到的点,更新从起点到每一个点的最短距离,min(dis[j], dis[t] + g[t][j])
    5. 重复第2步,直至所有存在最短路径的点更新完毕
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 510;
    int g[N][N];        // g[i][j]  i->j 的距离
    int dis[N];         // dis[i]   1->i 的最短距离
    bool vis[N];        // vis[i]   当前1->i 的最短距离是否确定
    int n,m;
    
    int dijkstra() {
        memset(dis, 0x3f, sizeof dis);
        dis[1] = 0;
        
        for(int i = 0; i < n; i++) {        // 访问 n 次
            int t = -1;
            for(int j = 1; j <= n; j++) {   // 访问 n 个点
                if(!vis[j] && (t == -1 || dis[t] > dis[j]))
                    t = j;
            }
            
            vis[t] = true;
            for(int j = 1; j <= n; j++)      //依次更新每个点所到相邻的点路径值
                dis[j] = min(dis[j], dis[t] + g[t][j]);
        }
        
         //如果第n个点路径为无穷大,不存在 1->n 最短路径
        if(dis[n] == 0x3f3f3f3f) return -1;
        return dis[n];
    }
    
    int main() {
        cin >> n >> m;
        memset(g, 0x3f, sizeof g);
        for(int i = 0; i < m ; i++) {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            g[x][y] = min(g[x][y],z);   //如果发生重边的情况则保留最短的一条边
        }
        
        cout << dijkstra() << endl;;
        return 0;
    }
    

    堆优化版本

    https://www.acwing.com/problem/content/852/

    在这里插入图片描述

    分析

    为什么说是用堆进行优化,因为在算法的第一步中,需要在没有确定最短路径的点中,找到从起点到该点距离最短的一个点。

    如果不加优化,这一步是O(n)的时间复杂度,但是如果使用小根堆的话,就可以优化为O(1),随后的一个pop操作,这是O(log n)的。整体来看,第一步可以优化为O(log n)

    随后,在进行松弛的过程中,最多有m条边,而入队操作的时间复杂度为O(log n),总体时间复杂度为O(m log n)

    在这里插入图片描述

    #include <iostream>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 5e5 + 10;
    int h[N], e[N], W[N], ne[N], idx;
    int dist[N];
    bool vis[N];
    int n,m;
    
    typedef pair<int,int> PII;
    
    void add(int u,int v,int k) {
        e[idx] = v, W[idx] = k, ne[idx] = h[u], h[u] = idx++;
    }
    
    int dijkstra() {
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
        
        priority_queue<PII, vector<PII>, greater<PII> > pq;     // 小根堆
        pq.push({0,1});
        
        while(!pq.empty()) {
            PII t = pq.top();
            pq.pop();
            
            int distance = t.first, ver = t.second;
            if(vis[ver]) continue;  // 排除当前节点已经找到最短路的情况
            vis[ver] = true;
            
            for(int i = h[ver]; i != -1 ; i = ne[i]) {
                int v = e[i];
                if(dist[v] > distance + W[i]) {
                    dist[v] = distance + W[i];
                    pq.push({dist[v],v});
                }
            }
        }
        
        if(dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }
    

    Dijkstra 算法 操作负权边的问题

    在这里插入图片描述
    因为Dijkstra算法每次都是在只在可以到达的没有确定最短路径的点中,找到一个最短的边,然后通过这个边,再去更新其他的点。

    就上面这个图来说,当存在负权边时,得到的最短路径为[0,-1,3],但显然应该是[0,-1,1]

    belloman-ford算法

    https://www.acwing.com/problem/content/855/

    在这里插入图片描述
    Bellman - ford算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。

    其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在 n-1 次松弛后还能更新,则说明图中有负环,因此无法得出结果

    算法执行流程

    在这里插入图片描述
    在松弛操作之前,需要对原本的数组进行拷贝,确保我们在松弛操作的时候,使用的是上一步松弛操作的结果,负责就会出现串联效应

    为什么说存在负环可能不存在最短路径

    因为belloman-ford算法,求的是单源的最短路径问题,那么对于负环的问题,只要负环不能到达终点,那么负环其实是对结果没有影响的。因为从起点到终点,已经确定了最多走k条

    但如果负环可以到达终点,那么任由负环一直循环下去,一定会把最短路径变为 -INF

    在这里插入图片描述

    Belloman-ford算法判断负环的方式

    我们一共有n个点,那么对于一个点来说,我最多松弛n-1次就可以找到一个最短路径,那么当我们继续第n次松弛的时候,如果还可以进行松弛,那就说明存在负权的回路

    判断路径是否可达

    在这里插入图片描述
    /2的原因是,0x3f3f3f3f是一个确定的值,并非真正的无穷大,会随着其他数值而受到影响,dist[n]大于某个与0x3f3f3f3f相同数量级的数即可。

    另外,根据题目的数据范围,负权边最多可以影响500 * 10000 次,但是0x3f3f3f3f远远大于这个数,所以说以此来判断是否存在最短路
    在这里插入图片描述

    源程序

    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 510, M = 1e4 + 10;
    int n,m,k;  // n个点,m条边,k 最多经过k条边
    int dist[N], backup[N];     // dist[i] 从1->i 的最短距离,backup dist的一个副本
    
    struct edges{
        int u,v,w;
    }e[M];
    
    int bellman_ford() {
        memset(dist, 0x3f, sizeof dist);
        dist[1] = 0;
        
        for(int i = 0; i < k; i++) {
            // 副本
            memcpy(backup,dist,sizeof dist);
            
            for(int i = 0; i < m; i++) {
                int u = e[i].u, v = e[i].v, w = e[i].w;
                dist[v] = min(dist[v], backup[u] + w);
            }
        }
        
        if(dist[n] >= 0x3f3f3f3f / 2) return -1;
        return dist[n];
    }
    
    int main() {
        cin >> n >> m >> k;
        for(int i = 0; i < m; i++) {
            cin >> e[i].u >> e[i].v >> e[i].w;
        }
        
        int t = bellman_ford();
        
        if(t == -1) puts("impossible");
        else cout << t << endl;
        
        return 0;
    }
    

    spfa算法

    https://www.acwing.com/problem/content/853/

    在这里插入图片描述
    在belloman-ford算法中,对于遍历的操作其实是有些多余的。因为对于那些没有更新的边,还是进行了一次判断,也就是判断了一些0x3f3f3f3f + w 的操作,显然是没有必要的
    在这里插入图片描述
    spfa算法在这个的基础上,对于松弛操作,利用宽度优先搜索做了一次优化,确保我们每次松弛的操作不会做一些无用功
    在这里插入图片描述

    时间复杂度 :n为点数,m为边数

    一般:O(m) 最坏:O(nm)(网格图的形式时,边权为特殊数值)

    #include <cstring>
    #include <algorithm>
    #include <queue>
    #include <iostream>
    
    using namespace std;
    
    const int N = 1e5 + 10;
    int h[N], e[N], w[N], ne[N], idx;
    int dist[N];
    bool vis[N];
    int n,m;
    
    void add(int u,int v,int k) {
        e[idx] = v, w[idx] = k, ne[idx] = h[u], h[u] = idx++;
    }
    
    int spfa() {
        memset(dist,0x3f,sizeof dist);
        dist[1] = 0;
        
        queue<int> que;
        que.push(1);
        vis[1] = true;
        
        while(!que.empty()) {
            int f = que.front();
            que.pop();
            
            vis[f] = false;
            
            for(int i = h[f]; ~i ; i = ne[i]) {
                int v = e[i];
                if(dist[v] > dist[f] + w[i]) {
                    dist[v] = dist[f] + w[i];
                    if(!vis[v]) {
                        que.push(v);
                        vis[v] = true;
                    }
                }
            }
        }
        
        if(dist[n] == 0x3f3f3f3f) return -1;
        return dist[n];
    }
    
    int main() {
        cin >> n >> m;
        memset(h,-1,sizeof h);
        
        for(int i = 0; i < m; i++) {
            int a,b,c;
            cin >> a >> b >> c;
            add(a,b,c);
        }
        
        int t = spfa();
    
        if(t == -1) puts("impossible");
        else cout << t << endl;
        return 0;
    }
    
    
    

    判断负环

    在判断负环的过程中,依据抽屉原理,我们统计每个点的访问次数,对于一个点,当他被访问了 n次的时候,也就是访问了n个边,即n + 1个点,这些点中肯定存在两个相同的点,所以说存在负环

    判断是否存在负环,并非判断是否存在从1开始的负环,因此需要将所有的点都加入队列中,更新周围的点

    返回true表示存在负环,false 表示不存在负环

    bool spfa() {
        memset(dist,0x3f,sizeof dist);
        
        queue<int> que;
        for(int i = 1; i <= n; i++) {
            que.push(i);
            vis[i] = true;
        }
        
        while(!que.empty()) {
            int f = que.front();
            que.pop();
            
            vis[f] = false;
            
            for(int i = h[f]; ~i ; i = ne[i]) {
                int v = e[i];
                if(dist[v] > dist[f] + w[i]) {
                    dist[v] = dist[f] + w[i];
                    cnt[v] = cnt[f] + 1;
                    if(cnt[v] >= n) return true;
                    
                    if(!vis[v]) {
                        vis[v] = true;
                        que.push(v);
                    }
                }
            }
        }
        
        return false;
    }
    

    Floyd算法

    在这里插入图片描述
    f[i, j, k]表示从``i走到j的路径上除ij点外只经过1k的点的所有路径的最短距离

    那么f[i, j, k] = min(f[i, j, k - 1), f[i, k, k - 1] + f[k, j, k - 1]

    因此在计算第k层的f[i, j]的时候必须先将第k - 1层的所有状态计算出来,所以需要把k放在最外层

    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 210, INF = 0x3f3f3f3f;
    int dist[N][N];
    int n,m,q;
    
    void floyd() {
        for(int k = 1; k <= n; k++)
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    }
    
    int main() {
        cin >> n >> m >> q;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(i == j)  dist[i][i] = 0;
                else dist[i][j] = INF;
        
        while(m --) {
            int x,y,z;
            cin >> x >> y >> z;
            dist[x][y] = min(dist[x][y],z);
        }
        
        floyd();
        
        while(q--) {
            int x,y;
            cin >> x >> y;
            if(dist[x][y] >= INF / 2) puts("impossible");
            else cout << dist[x][y] << endl;
        }
        return 0;
    }
    
    展开全文
  • 十一长假后,同学们陆续开始做题,现在月底了,扩展题“-二值矩阵避障最短路径算法”只有7人上交了作业,其中能够运行的有2人,分别是电子18级邵华薇同学、软工18级唐宇。这里提出表扬。 题目可能是有些难度,是我的...

    十一长假后,同学们陆续开始做题,现在月底了,扩展题“-二值矩阵避障最短路径算法”只有7人上交了作业,其中能够运行的有2人,分别是电子18级邵华薇同学、软工18级唐宇。这里提出表扬。

    题目可能是有些难度,是我的责任。不过,即使做不完,大家以后还是应该提交一个版本的代码,让老师们知道大家已经在思考了。如果不抓住本科难得的时间,没有工作压力的情况下专心思考,今后步入公司后,压力会更大。


    题目:一个迷宫,用64x64的二维数组表示,值为1的元素表示平地,值为0的表示砖墙。现在,给定起点、终点,要求从起点走到终点,尽可能走最短距离。走位要求:在空白区域,可以朝着任意方向走,只要不碰到砖墙即可。

    我们可以把这个题目分为两部分。第一部分,是如何走到终点;第二部分,是距离尽可能的短。对于如何走到终点的问题,可以使用启发搜索的算法;第二部分,在第一部分的基础上,做直线归并。

    我把两位同学的代码整合为一个demo,参见 https://codechina.csdn.net/coloreaglestdio/qtcpp_demo/-/tree/master/floodfill_mdf

    1. 找到一条路径

    这里采用邵华薇同学的算法稍加改进,分为反向探路、前向回溯两步。
    反向探路:
    1、首先从终点开始,朝着东南西北四个方向步进,每次只走一格。
    2、每个走到的空白格子里,填写当前的步数。
    3、以当前走到的位置为种子,递增步数,重复上述过程,直到找到起点为止。
    记录步数的矩阵需要独立设置,障碍物、没有走到的区域全部初始化为无穷大。
    前向回溯:
    从起点开始,从当前位置沿着8个方向(东南西北、东南、东北、西北、西南)寻找步数最小的一个格子,记录下来,并挪动当前位置到该格子,直到回到终点。

    通过这两步,就可以找到一条路径,如下图所示:
    直接路径求取

    2.归并直线路径

    由于上述寻找的方向只是8个方向,显然路径中存在更短的捷径。找直线的方法,可以直接使用唐宇的思路,即穷尽法。当然,还有更有启发性的梯度下降,但同学们首先还是应该掌握简单的方法。

    原理:不断的试探路线上的两点连线会不会被方块阻碍。如不会,则合并连线,产生新的轨迹。程序中有几个小的优化,用于在障碍周围精细地规避,以及避免整形舍入的误差。
    直线归并

    代码

    绘图代码从 仓库 签出。

    展开全文
  • Dijkstra最短路径算法详解

    千次阅读 2015-08-06 00:26:44
    简介Dijkstra最短路径算法是非常经典的图搜索算法,而且具有一定难度,需要花时间好好理解。算法导论第24章对此有详细的分析,值得研究一番。而我自己也结合一个具体实例,实现了代码,确实只有在编码的过程中才能...
  • 9-1 最短路径问题和松弛操作 图 例如:路径规划,工作任务规划。 之前说讲过的广度优先遍历: 图 其实求出的是一个点(起点)到其他顶点的最短路径问题,通过BFS,得到了一棵树,这棵树就叫做最短路径树(shortest...
  • Bellman - ford算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在n-1次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则...
  • 举例来说,如果图中的顶点表示城市,而边上的权重表示城市间开车行经的距离,该算法可以用来找到两个城市之间的最短路径算法过程 我们用一个例子来具体说明迪杰斯特拉算法的流程。 定义源点为 0,dist[i]为源点 ...
  • Bellman-Ford算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在n-1次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就...
  • 针对已有LFA实现方式计算开销大和部署难度高的问题,提出了一种基于增量最短路径优先算法的LFA实现方法(LFA implementation method based on incremental shortest path first algorithm,ERPISPF)。首先将快速...
  • 暑假,小哼准备去一些城市旅游。有些城市之间有公路,有些城市之间则没有。为了节省经费以及方便计划旅程,小哼希望在出发之前知道任意两个城市之前的最短路程。
  • 图的最短路径算法 最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 算法具体的形式包括: 确定起点的最短路径问题:即已知起始结点,求最短路径的问题。...
  • 本文介绍求最短路径的一个经典算法——Dijkstra算法,它由荷兰图灵奖获得者、计算机科学家Dijkstra于1959年提出。该算法能够有效地计算出某个特定顶点(称为源点),到其余所有顶点的最短路径,即它能够很好地解决...
  • 所以,如果要求的是所有点对间的最短路径,或者如果数据范围较小,则Floyd算法比较合适。  Dijkstra算法最大的弊端是它无法适应有负权边的图。但是Dijkstra算法具有良好的可扩展性,扩展后可以适应很多问题。 ...
  • Floyd算法是解决求图中所有顶点到所有顶点的最短路径,时间复杂度是。Dijkstra算法是求从某个源点到其余各顶点的最短路径问题,时间复杂度是,如果求图中所有顶点到所有顶点的最短路径,需要再运行n次Dijkstra函数,...
  • 自从上一篇博客详细讲解了Python遗传和进化算法工具箱及其在带约束的单目标函数值优化中的应用之后,我经过不断学习工具箱的官方文档以及对源码的研究,逐步更加地掌握如何利用遗传算法求解更多有趣的问题了。...
  • 最短路径算法一之Dijkstra算法算法描述:在无向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到由顶点 V0 到其余各点的最短路径。 使用条件:单源最短路径,适用于边权非负的情况Dijkstra算法求最短路径具体...
  •  最短路径算法,顾名思义就是求解某点到某点的最短的距离、消耗、费用等等,有各种各样的描述,在地图上看,可以说是图上一个地点到达另外一个地点的最短的距离。比方说,我们把地图上的每一个城市想象成一个点,从...
  • 文章目录一 前言二 Dijkstra 算法讲解1. 贪心算法的证明2. 算法实现说明3. 初版Dijkstra算法代码三 时间复杂度优化1. 优化策略2....一 前言   上一次的文章更新...   本次记录的是最短路径算法中的单源最短路经Dijkst
  • 诶,向下走到了(2,1),诶,发现我现在怎么走都走不通了,我就吧(2,1)变成了3,回到了(1,1),好这条路不通我继续找另一条路,诶,我发现我无路可走了,那我把(1,1)也设置为3,就没了 最短路径问题 小球得到的路径,和...
  • 我们知道,Dijkstra是解决单源最短路问题的,并且最基本的算法仅能求出最短路的长度,而不能输出路径,本文基于Dinjkstra进行改进,使之能记录源点到任意点的所有最短路径。使用vector来记录一条路径,因为每个结点...
  • 人们生活节奏也在不断的加快,对于网络的依赖也越来越紧密,尤其是在等公交,经常会错过班次,但又不知道,下次班次几点发车,这样会导致乘客花掉大把时间在等待,如果可以掌握发车动态及最短乘车路径,乘客就可以...
  • 贪心算法之单源最短路径

    千次阅读 2017-04-19 20:38:55
     最短路径算法,顾名思义就是求解某点到某点的最短的距离、消耗、费用等等,有各种各样的描述,在地图上看,可以说是图上一个地点到达另外一个地点的最短的距离。比方说,我们把地图上的每一个城市想象成一个点,从...
  • - ford(贝尔曼-福特)算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在n-1次松弛后还能更新,则说明图中有负环,因此无法得出结果...
  • 显然,对于问题:所有结点对的最短路径问题,我们需要找到图中任何两个结点间的最短路径。同时,我们能轻易得对上一章所学的Bellman_Ford或是Dijkstra算法对每个结点都调用一次而得出结果——但显然,将会浪费很多...
  • 最短路径1.1 迪杰斯特拉(Dijkstra)算法1.2 佛洛依德(Floyd)算法2. 总结 前言 部分内容摘自程杰的《大话数据结构》 1. 最短路径   我们时常会面临着对路径选择的决策问题。例如在北京、上海、 广州等城市,因...
  • 现在,我们准备介绍计算机科学史上伟大的成就之一:Dijkstra最短路径算法[1]。这个算法适用于边的长度均不为负数的有向图,它计算从一个起始顶点到其他所有顶点的最短路径的长度。在正式定义这个问题(3.1节)之后,...
  • 对无权图进行广度优先遍历,最终会形成一棵生成树,称为最短路径树(相当于有权图中的最小生成树),即解决了无权图单源最短路径问题(求从一个节点到其它所有可到达节点的最短路径) 有权图的最短路径问题,核心...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,558
精华内容 3,023
关键字:

最短路径的算法难度