DDR爱好者之家

Python实现迪杰斯特拉算法并生成最短路径的示例代码
站长资源 2024/11/24 佚名
12 1538
DDR爱好者之家 Design By 杰米
def Dijkstra(network,s,d):#迪杰斯特拉算法算s-d的最短路径，并返回该路径和代价
  print("Start Dijstra Path……")
  path=[]#s-d的最短路径
  n=len(network)#邻接矩阵维度，即节点个数
  fmax=999
  w=[[0 for i in range(n)]for j in range(n)]#邻接矩阵转化成维度矩阵，即0→max
  book=[0 for i in range(n)]#是否已经是最小的标记列表
  dis=[fmax for i in range(n)]#s到其他节点的最小距离
  book[s-1]=1#节点编号从1开始，列表序号从0开始
  midpath=[-1 for i in range(n)]#上一跳列表
  for i in range(n):
    for j in range(n):
      if network[i][j]!=0:
        w[i][j]=network[i][j]#0→max
      else:
        w[i][j]=fmax
      if i==s-1 and network[i][j]!=0:#直连的节点最小距离就是network[i][j]
        dis[j]=network[i][j]
  for i in range(n-1):#n-1次遍历，除了s节点
    min=fmax
    for j in range(n):
      if book[j]==0 and dis[j]<min:#如果未遍历且距离最小
        min=dis[j]
        u=j
    book[u]=1
    for v in range(n):#u直连的节点遍历一遍
      if dis[v]>dis[u]+w[u][v]:
        dis[v]=dis[u]+w[u][v]
        midpath[v]=u+1#上一跳更新
  j=d-1#j是序号
  path.append(d)#因为存储的是上一跳，所以先加入目的节点d，最后倒置
  while(midpath[j]!=-1):
    path.append(midpath[j])
    j=midpath[j]-1
  path.append(s)
  path.reverse()#倒置列表
  print(path)
  #print(midpath)
  print(dis)
  #return path

network=[[0,1,0,2,0,0],
     [1,0,2,4,3,0],
     [0,2,0,0,1,4],
     [2,4,0,0,6,0],
     [0,3,1,6,0,2],
     [0,0,4,0,2,0]]
Dijkstra(network,1,6)

以上就是Python实现迪杰斯特拉算法并生成最短路径的示例代码的详细内容，更多关于Python实现迪杰斯特拉算法的资料请关注其它相关文章！

DDR爱好者之家 Design By 杰米
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
DDR爱好者之家 Design By 杰米
ddrfans.com DDR爱好者之家
8,675无损音乐
1,324高清电影
213破解软件
70,141收录资讯

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。

《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。

更新日志

友情链接

杰晶网络 DDR爱好者之家 南强小屋 黑松山资源网 白云城资源网
DDR爱好者之家 Design By 杰米