文章
10
粉丝
165
获赞
7
访问
26.2k
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:
① 设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;
② 选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点u=v;
③ 重复步骤②,直到u是目标顶点时为止。
登录后发布评论
暂无评论,来抢沙发