摘要
在道路网络中确定起点到终点的最短路径,可以抽象为一个有向图模型。图中每个节点表示一个“路口”,对任意节点u,v,存在uv-边当且仅当从u到v有“路段”直接相连(当中没有其他路口)。也可以建立无向图模型,则任一条边对应于双向可通行的路段。其实这样的模型并不限于道路交通问题,从本专栏前面的文章中读者已经看到许多与交通运输无关的问题都可以抽象为图模型,“最短路径”在不同应用中可能背景意义不同,但确定最短路是大量基于图模型的应用问题求解中的一个基本环节。
出处
《中国信息技术教育》
2020年第13期18-22,共5页
China Information Technology Education
