试题详情
简答题请简述Dijkstra算法及其在GIS最短路径分析中的应用？
  • Dijkstra算法是按路径长度递增顺序产生各顶点的最短路径。
    算法过程：设最短距离已确定的顶点集合称为红集点，最短距离尚未确定的为蓝集点。
    1）按路径长度递增顺序产生
    各蓝顶点的最短路径；
    2）在当前蓝点集中选择一个距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的顺序产生各顶点的最短路径；
    3）没扩充一个蓝点到红点集中，则剩余的蓝点的路径按照新加入的红点作为中间顶点进行修正，一旦加入新顶点使得蓝点路径长度最短，则用变短的路径代替原来的蓝点路径长度，重复以上过程；
    4）直到所需求的蓝点已扩充到红点集时，算法结束。
    应用：
    1）选择要进行计算的两个结点；
    2）对这两个结点进行联通分析，即采用宽度优先搜索方法，来快速判断这两个结点之间是否联通，也就是确定是否存在计算最短路径的必要，若联通则进行
    3）调用Dijkstra算法，计算两个结点之间的最短路径
    4）进过对计算出来的最短路径树进行优化处理后，生成最终的最短路径树，输出并推出。

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

热门试题