日志
最短路径算法概述
|
--备忘--
最短路问题：
最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。
数学定义:
一个有权重的有向图 G，以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 u 到 v 有路径相连。我们以 E 表示G中所有边的集合，而边的权重则由权重函数 w: E → [0, ∞] 定义。因此，w(u, v) 就是从顶点 u 到顶点 v 的非负权重（weight）。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。
最短路径问题的主要形式包括：
确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。适合使用Dijkstra算法。
确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。
全局最短路径问题 - 求图中所有的最短路径。适合使用Floyd-Warshall算法。
最常用的路径算法有：
Dijkstra算法 （不存在负边）
A*算法
Bellman-Ford算法（Bellman-Ford算法--能存在负权边的情况下解决单源点最短路径问题）
SPFA算法 (Bellman-Ford算法的改进版本)
Floyd-Warshall算法（Floyd-Warshall算法是解决任意两点间的最短路径的一种算法，它需要用邻接矩阵来储存边。通常可以在任何图中使用，包括有向图、带负权边的图。）
Johnson算法（Johnson算法适用于求All Pairs Shortest Path. Johnson算法应用了重标号技术，先进行一次Bellman-Ford算法，然后对原图进行重标号，w'(i,j)=h[i]-h[j]+w(i,j)。然后对每个点进行一次Dijkstra，每次Dijkstra的复杂度为O(nlogn+m)，于是算法复杂度为O(n^2logn+m)）
Bi-Direction BFS算法
已同步至 风树的微博