试题详情
简答题什么是最短路径？简述经典的最短路径算法过程。
  • 最短路径：就是指在带权有向图中，寻找从指定起点到终点的一条具有最小权值总和的路径。
    经典的最短路算法
    一、迪杰斯特拉（Dijkstra）算法：
    由荷兰数学家E.W.Dijkstra于1959年提出的一个适用于非负权值网络的单源最短路算法，是目前求解最短路问题的理论上最完备、应用最广的经典算法，它可以给出从某指定节点到图中所有其他节点的最短路。
    迪杰斯特拉（Dijkstra）算法主要思想是：按照路径长度逐点增长的方法构造一棵路径树，从而得到从该树的根节点（即指定起点）到其它所有节点的最短路。
    按路径长度递增次序产生最短路径算法：
    把V分成两组：
    （1）S：已求出最短路径的顶点的集合
    （2）V-S=T：尚未确定最短路径的顶点集合
    将T中顶点按最短路径递增的次序加入到S中，
    保证：
    （1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度
    （2）每个顶点对应一个距离值
    S中顶点：从V0到此顶点的最短路径长度
    T中顶点：从V0到此顶点的只包括S中顶点作中间
    顶点的最短路径长度
    求最短路径步骤
    1、初始时令S={V0}，T={其余顶点}，T中顶点对应的距离值
    1）若存在0，Vi>，为0，Vi>弧上的权值
    2）若不存在0，Vi>，为μ
    2、从T中选取一个其距离值为最小的顶点W，加入S
    3、对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值
    4、重复上述步骤，直到S中包含所有顶点，即S=V为止

    二、弗洛伊德（Floyd）算法
    算法思想：逐个顶点试探法
    求最短路径步骤
    初始时设置一个n阶方阵，令其对角线元素为0，若存在弧，则对应元素为权值；否则为μ
    逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值
    所有顶点试探完毕，算法结束

  • 关注下方微信公众号，在线模考后查看

热门试题