时间耗费最少路径算法研究  

作　　者：王学军 孙荣霞[1] 马少卿 沈文博 

机构地区：[1]河北大学电子信息工程学院

出　　处：《电子世界》2017年第21期59-59,61,共2页Electronics World

摘　　要：经典的Dijkstra、Floyd最短路径算法不能很好的描述日益变化的现代城市交通网络。本研究将所在城市交通网络图按照划分的N个限制搜索区域,在每个限制搜索区域中应用k-Means算法对该区域的交通流状况进行聚类分析以得分类簇。在每一个分类簇中,以该簇中各个边的时间耗费以及结点耗费作为边的权重,替代经典最短路径算法中边的距离权重,得到时间耗费最少路径算法。在网络规模日益扩大情况下,通过采集2周实际交通数据进行仿真实验,本算法取得良好效果。

关 键 词：最短路径 K-MEANS聚类 城市交通网络图 时间耗费 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]