迷宫最短路径算法

6.3.3 最短路径算法--Dijkstra算法，Bellmanford算法，Floyd算法，Johnson算法

最短路径算法

在交通地图上，两地点之间的路径通常标有长度，我们可以用加权有向来描述地图上的交通网。加权有向图中每条路径都有一个路径权值，大小为该路径上所有边的权值之和。本节将重点讨论顶点之间最短路径问题。在实际问题中，路径权值还可以表示其它类型的开销，例如两地之间行程所需要的时间；两任务切换所需代价等。

本节讨论的最短路径具有方向性，问题用图的术语描述为：给定一个起始顶点s和一个结束顶点t，在图中找出从s到t的一条最短路径。称s为路径源点，t为路径汇点。

最短路径问题可以进一步分为单源最短路径和全源最短路径。

单源最短路径定义为，给定起始顶点s，找出从s到图中其它各顶点的最短路径。求解单源最短路径的算法主要是Dijkstra算法和Bellman-Ford算法，其中Dijkstra算法主要解决所有边的权为非负的单源最短路径问题，而Bellman-Ford算法可以适用于更一般的问题，图中边的权值可以为负。

全源最短路径定义为，找出连接图中各对顶点的最短路径。求解全源最短路径的算法主要有Floyd算法和Johonson算法，其中Floyd算法可以检测图中的负环并可以解决不包括负环的图中的全源最短路径问题；Johonson算法同样也是解决不包含负环的图的全源最短路径问题，但是其算法效率更高。

1 基本原则

最短路径算法具有最短路径的最优子结构性质，也就是两顶点之间的最短路径包括路径上其它顶点的最短路径。具体描述为：对于给定的带权图G=(V, E)，设p=是从v1到vk的最短路径，那么对于任意i和j，1≤i≤j≤k，pij=为p中顶点vi到vj的子路径，那么pij是顶点vi到vj的最短路径。

最短路径算法都使用了松弛(relaxation)技术。开始进行一个最短路径算法时，只知道图中边和权值。随着处理逐渐得到各对顶点的最短路径的信息。算法会逐渐更新这些信息，每步都会检查是否可以找到一条路径比当前给定路径更短。这一过程通常称为“松弛”。

例7.4 最短路问题 给定N个点),,2,1(Nipi组成集合}{ip，由集合中任一点ip到另一点jp的距离用ijc表示，如果ip到jp没有弧联结，则规定ijc，又规定)1(0Nicii，指定一个终点Np，要求从ip点出发到Np的最短路线。这里我们用动态规划方法来做。用所在的点ip表示状态，决策集合就是除ip以外的点，选定一个点jp以后，得到效益ijc并转入新状态jp，当状态是Np时，过程停止。显然这是一个不定期多阶段决策过程。

定义)(if是由ip点出发至终点Np的最短路程，由最优化原理可得

0)(1,,2,1)},({min)(NfNijfcifijj

这是一个函数方程，用LINGO可以方便的解决。

!最短路问题;

model:

data:

n=10;

enddata

sets:

cities/1..n/: F; !10个城市;

roads(cities,cities)/

1,2 1,3

2,4 2,5 2,6

3,4 3,5 3,6

4,7 4,8

5,7 5,8 5,9

6,8 6,9

7,10

8,10

9,10

/: D, P;

endsets

data:

D=

6 5

3 6 9

7 5 11

9 1

8 7 5

4 10

5

7

9;

enddata

F(n)=0;

@for(cities(i) | i #lt# n:

F(i)=@min(roads(i,j): D(i,j)+F(j));

);

!显然，如果P(i,j)=1,则点i到点n的最短路径的第一步是i --> j，否则就不是。

由此，我们就可方便的确定出最短路径;

龙源期刊网

最短路径算法研究

作者：李鲁平

来源：《科学与财富》2016年第09期

摘要：最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法，本文主要对其中的两种：Dijkstra和Floyd-Warshall进行研究和分析实现。

关键词：算法；动态规划；最短路径；编程开发

0 引言

在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：

（1）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。

（2）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

（3）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。

（4）全局最短路径问题：求图中所有的最短路径。

用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、SPFA算法。Floyd-Warshall算法是求多源、无负权边的最短路，用矩阵记录图，时效性较差，时间复杂度O（V^3）。Dijkstra算法是求单源、无负权的最短路的算法，时效性较好，时间复杂度为O（V*（V+E）），可以用优先队列进行优化，优化后时间复杂度变为O（v*lgn）。Bellman-Ford算法求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（V*E）。SPFA算法是对Bellman-Ford算法的队列优化，时效性相对好，时间复杂度O（kE）。本文主要研究Dijkstra和Floyd-Warshall算法细节。

龙源期刊网

一种电脑鼠走迷宫算法

作者：周杰

来源：《电脑知识与技术》2018年第03期

摘要：该文通过对电脑鼠走迷宫算法的研究，提出了一种电脑鼠走迷宫算法，该算法引用了斜线K和Z用以更新期望坐标，并将迷宫分割为多个部分，以斜线K上的点为起点坐标，下一条斜线K上的点为期望终点坐标，找到起点坐标和终点坐标的最优解，以局部最优，引出全局最优找到最佳路径，并与传统走迷宫算法进行比较，提高了迷宫搜索效率。

关键词：迷宫；斜线；局部最优；最佳路径

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）03-0053-03

1 概述

电脑鼠是一种机电一体化装置，是由单片机、传感器、机电运动部件组成的一种能在迷宫行走的小型机器人可以通过预先设定的算法，探索迷宫，可以找到一条从预设的起点到终点的最佳路径，运行环境是由一个16X16正方形单元格所组成的迷宫，其中单元格的大小为18cmX18cm，文献[1][2]给出了电脑鼠走迷宫的相关规则，每一个单元格有相应的挡板组成，电脑鼠的目的是在最短的时间内找到出口，在整个电脑鼠中最重要的是硬件的可靠性和算法的优劣，在当今单片机迅速发展的时代，硬件稳定性上已经趋于稳定，本文主要研究和设计搜索迷宫算法，并提出了一种电脑鼠搜索迷宫的算法。

2 迷宫环境建模

电脑鼠不具有思维能力，它只能按照我们设定的算法运行，因此需要模拟现场运行环境[6][7].

构建一个16X16的迷宫，迷宫的水平方向为Y轴，垂直方向为X轴，第一个坐标为（1，1），那么依次下去最上角的坐标为（16，16）。迷宫构建图，如图1 所示，迷宫内的挡板信息未知。

假设起点为（1，1）终点为（16，16），现在规定，X方向为地理北，Y方向为地理南，如图2所示。