算法:最短路径问题

  created  by  Sherlock {{tag}}
创建于 2019年03月30日 21:56:45 最后修改于 2018年10月30日 12:10:04

算法:最短路径问题

算法:最短路径问题

    最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。算法具体的形式包括:

(1)确定起点的最短路径问题- 即已知起始结点,求最短路径的问题。适合使用Dijkstra算法

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

(3)确定起点终点的最短路径问题- 即已知起点和终点,求两结点之间的最短路径

(4)全局最短路径问题- 求图中所有的最短路径。适合使用Floyd-Warshall算法

    数据结构——图

    图是由顶点集合以及顶点间的关系集合组成的一种数据结构。可以写作Graph = (V,E)  V是顶点的又穷非空集合;E是顶点之间关系的有穷集合,也叫边集合。图分为有向图和无向图,有向图的边也被称作,可以用集合表示一个图的边或是弧:边集合{(A,B),(B,C)},弧集合{<A,B>,<B,A>},当边和弧加权,图被称作网。

    我们要解决的最短路径问题就是基于网这一数据结构的,


2018-10-30Sherlock