一种网络图中最短路径的二分查找追踪方法

摘要

本发明公开了一种网络图中最短路径的二分查找追踪方法，特征是根据最短路径步数矩阵提取源节点到汇节点的最短路径步数，对其折半拆分为前、后步数；在最短路径步数矩阵的源节点行向量中搜索步数等于前步数的节点，为前步数节点集；在最短路径步数矩阵的汇节点列向量中搜索步数等于后步数的节点，为后步数节点集；取前、后步数节点集的交集为中间节点；以交集中每节点为基准，用上述方法求源节点与该节点、该节点与汇节点的中间节点，直到需求解节点间最短路径步数为1为止；将所求的中间节点顺次插到对应位置得源到汇节点的所有最短路径；利用本发明方法查找两点间所有最短路径，可对应于实际数据中抽象出网络图的择优路径选择提供多种方案。