电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

Dijkstra算法示例

Dijkstra算法示例_第1页
1/6
Dijkstra算法示例_第2页
2/6
Dijkstra算法示例_第3页
3/6
Dijkstra 算法 我们想找到A 与E(下图)之间的最佳路由。可以看到A 与E 之间有六条可能路径(ABE、ACE、ABDE、ACDE、ABDCE、ACDBE),很明显 ABDE 是最佳路由,因为它的权值最小。但是实际情况并非总是如此简单,有很多复杂的情形需要使用算法来找到最佳路由。 1. 如下图所示,源节点(A)被选为 T 节点,所以它的标号是永久(我们将永久性节点以实圈标注,T 节点以-->符号标注)。 2. 在这一步中,直接链接到T 节点的暂时性节点(B, C)的状态记录集已经被修改。同时,由于 B 有更小的权值,所以它被选作 T 节点,其标号被改为永久(如下图所示)。 3. 与步骤 2 类似,在这一步中,直接链接到T 节点的暂时性节点(D, E)的状态记录集已经被修改。同时,由于 D 有更小的权值,所以它被选作 T 节点,其标号被改为永久(如下图所示)。 4. 在这一步中,已经没有任何暂时性节点,所以我们仅仅需要确认下一个 T 节点。因为 E 有最小权值,所以它被选作 T 节点。 5. E 是目的节点,所以我们在这里停止。 我们已经到达了终点!现在,我们需要确定路由。E 的前序节点是D,D 的前序节点是B,B的前序节点是A。所以最佳路由是ABDE。在这个案例中,权值和为 4(1+2+1)。

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

Dijkstra算法示例

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部