python实现Dijkstra静态寻路算法

站长资源 2024/11/26 佚名

2 0 1

算法介绍

迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

当然目前也有人将它用来处理物流方面，以获取代价最小的运送方案。

算法思路

Dijkstra算法采用的是一种贪心的策略。

1.首先，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合T。
2.其次，原点 s 的路径权重被赋为 0 （dis[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。初始时，集合T只有顶点s。
3.从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，此时完成一个顶点。
4.再次，看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。
5.最后，从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点（可以到达的）。

算法图形演示

现在有图如下：

每个线的权重以及标识如图所示。

第一步：

建立dis数组和T数组。
首先从起点A 开始，将A可以直接到达的顶点的权重记录在dis数组中，无法直达的记录无穷大（当前使用FFFF表示无穷大）。

将当前选择的顶点加入数组T:

第二步：

从dis数组中选择一个不在T数组中的顶点的最小权重值的顶点，当前选择为B顶点，并将B可以直接到达的顶点的相关权重和当前dis中的权重值比较，如果当前dis权重值大，则替换：

将B加入数组T:

第三步：

依次选择顶点C：

将C加入数组T:

第四步：

依次选择顶点D：

将D加入数组T:

第五步：

依次选择顶点E：

将E加入数组T:

第六步：

依次选择顶点F：

将F加入数组T:

因为所有的顶点都已经在T数组中了，算法结束。
这样就求得了从A点到各个顶点的最优解。

可以看到A顶点无法直达F顶点。

代码表示：

(代码中使用999代表FFF)

#encoding:utf-8

import copy
"""
图的表示方式
邻接矩阵
999代表无限远
"""
tuG=[[0, 10, 20, 999, 999, 999],
 [999, 0, 999, 20, 70, 999],
 [999, 999, 0, 50, 30, 999],
 [999, 999, 999, 0, 999, 999],
 [999, 999, 999, 10, 0, 999],
 [999, 999, 999, 20, 20, 0]];

tuX = 6;

# 设置原点到其他定点的各个距离
dis = copy.deepcopy(tuG[0]);

def Dijkstra(G,v0):
 """
 使用 Dijkstra 算法计算指定点 v0 到图 G 中任意点的最短路径的距离
 INF 为设定的无限远距离值
 """
 t = [];
 minv = v0;

 while len(t) <= tuX:
 t.append(minv);
 #以当前点的中心向外扩散
 for w in range(0, tuX):
  if dis[minv] + G[minv][w] < dis[w]:
  dis[w] = dis[minv] + G[minv][w]

 tmp = 1000;
 for i in range(0, tuX):
  tmpFlag = False;
  for j in range(0, len(t)):
  if i == t[j]:
   tmpFlag = True;
   break;

  if tmpFlag == True:
  continue;

  if tmp > dis[i]:
  tmp = dis[i];
  minv = i;

if __name__ == '__main__': 
 Dijkstra(tuG,0); 
 print dis;

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

python,Dijkstra,静态寻路

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！

评论“python实现Dijkstra静态寻路算法”

暂无评论...

www.wwsws.com 伏龙阁资源网

39,976影音资源

44,792技术资源

21,817软件资源

651,128站长资源

稳了！魔兽国服回归的3条重磅消息！官宣时间再确认！

昨天有一位朋友在大神群里分享，自己亚服账号被封号之后居然弹出了国服的封号信息对话框。

这里面让他访问的是一个国服的战网网址，com.cn和后面的zh都非常明白地表明这就是国服战网。
而他在复制这个网址并且进行登录之后，确实是网易的网址，也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情，因为以前都没有出现这样的情况，现在突然提示跳转到国服战网的网址，是不是说明了简体中文客户端已经开始进行更新了呢？

更新日志

2024年11月26日

python实现Dijkstra静态寻路算法

Python设计模式之模板方法模式实例详解

Python设计模式之外观模式实例详解

评论“python实现Dijkstra静态寻路算法”

稳了！魔兽国服回归的3条重磅消息！官宣时间再确认！

更新日志

友情链接