大型电子商务网站 服务器硬件 cpu 内存 硬盘 2014,美食网站开发意义,公司网页介绍,东莞高端做网站使用场景Dijkstra算法用于解决单源点最短路径问题#xff0c;即给一个顶点作为源点#xff0c;依次求它到图中其他n-1个顶点的最短距离。例题讲解Dijkstra算法将图中所有顶点分成两部分#xff0c;第一部分是已知到源点最短距离的顶点Known(K)#xff0c;第二部分是不知道到…使用场景Dijkstra算法用于解决单源点最短路径问题即给一个顶点作为源点依次求它到图中其他n-1个顶点的最短距离。例题讲解Dijkstra算法将图中所有顶点分成两部分第一部分是已知到源点最短距离的顶点Known(K)第二部分是不知道到源点最短距离的顶点Unknown(U)。初始化K中只有源点一个顶点U中有n-1个顶点。如下图我们求源点1到终点7的最短路径。根据上图可以得到如下表KK中顶点到源点的距离UU中顶点到源点的距离102无穷3无穷4无穷5无穷6无穷7无穷1-1. 找到顶点1的邻接点2和3然后更新它们到源点1的距离得到下表KK中顶点到源点的距离UU中顶点到源点的距离1022354无穷5无穷6无穷7无穷1-2. 更新K,U中的顶点。发现U中2到源点的距离最小把2加入K中得到下表KK中顶点到源点的距离UU中顶点到源点的距离1035224无穷5无穷6无穷7无穷2-1. 找到2的邻接点4和5更新它们到源点的距离得到下表KK中顶点到源点的距离UU中顶点到源点的距离1035224628582106无穷7无穷2-2. 更新K,U中的顶点。发现U中3到源点距离最小把3加入K中得到下表KK中顶点到源点的距离UU中顶点到源点的距离104822510356无穷7无穷3-1. 找到3的邻接点4和6更新它们到源点的距离得到下表KK中顶点到源点的距离UU中顶点到源点的距离1045162251035665117无穷3-2. 更新K,U中的顶点。发现U中4到源点的距离最短把4加入K中得到下表KK中顶点到源点的距离UU中顶点到源点的距离1051022611357无穷464-1. 找到4的邻接点5和6更新它们到源点的距离得到下表KK中顶点到源点的距离UU中顶点到源点的距离105268226167357无穷464-2. 更新K,U中的顶点。发现6到源点的距离最短把6加入K中加入得到下表KK中顶点到源点的距离UU中顶点到源点的距离1058227无穷3546675-1. 找到6的邻接点7更新7到源点的距离得到下表KK中顶点到源点的距离UU中顶点到源点的距离105822776133546675-2. 更新K,U中的顶点。K中5到源点的距离最小把5加入K中得到下表KK中顶点到源点的距离UU中顶点到源点的距离1071322354667586-1. 找到5的邻接点7,更新7到源点的距离得到下表KK中顶点到源点的距离UU中顶点到源点的距离107381122354667586-2. 更新K,U中的顶点将顶点7加入K中完成计算得到下表KK中顶点到源点的距离UU中顶点到源点的距离102235466758711由此我们就得到源点1到各个顶点的最短路径。
