Python使用Dijkstra算法实现求解图中最短路径距离问题详解

本文实例讲述了Python使用Dijkstra算法实现求解图中最短路径距离问题。分享给大家供大家参考，具体如下：

这里继续前面一篇《Python基于Floyd算法求解最短路径距离问题》的内容，这里要做的是Dijkstra算法，与Floyd算法类似，二者的用途均为求解最短路径距离，在图中有着广泛的应用，二者的原理都是老生常谈了，毕竟本科学习数据结构的同学是不可能不学习这两个算法的，所以在这里我也不再累赘，只简单概述一下这个算法的核心思想：

Dijkstra算法的输入有两个参数，一个是原始的数据矩阵，一个是起始的顶点下标，算法的思想也很简单容易理解，在开始的时候，需要设置两个集合，用于存储顶点和路径距离，假设为A、B，A中最开始只包含有起始顶点，B中包含有其他所有的顶点，并且B中的顶点路径的距离均为A中的起始顶点到B中各个顶点的路径距离值，之后从B中找到最短的路径，将该路径的在B的一端的顶点加入到A中，更新B中对应的路径距离，循环往复进行下去直到遍历完B中的顶点为止。

好了，又啰嗦了这么多了，下面看一下，python实现的Dijkstra算法，我现在做的只是简单的回顾一下这些算法，并没有去优化或者深究，所以程序都是很简单很LOW，希望见谅，毕竟水平有限，但是能达到看一遍能明白什么意思：

#!usr/bin/env python
#encoding:utf-8
'''''
__Author__:沂水寒城
功能：使用Dijkstra算法求最短路径距离
'''
import random
import time
def random_matrix_genetor(vex_num=10):
  '''''
  随机图顶点矩阵生成器
  输入：顶点个数，即矩阵维数
  '''
  data_matrix=[]
  for i in range(vex_num):
    one_list=[]
    for j in range(vex_num):
      one_list.append(random.randint(1, 100))
    data_matrix.append(one_list)
  return data_matrix
def dijkstra(data_matrix, start_node):
  '''''
  Dijkstra求解最短路径算法
  输入：原始数据矩阵，起始顶点
  输出；起始顶点到其他顶点的最短距离
  '''
  vex_num=len(data_matrix)
  flag_list=['False']*vex_num
  prev=[0]*vex_num
  dist=['0']*vex_num
  for i in range(vex_num):
    flag_list[i]=False
    prev[i]=0
    dist[i]=data_matrix[start_node][i]
  # print '----------------------------------------------------'
  # print flag_list
  # print prev
  # print dist
  flag_list[start_node]=False
  dist[start_node]=0
  k=0
  for i in range(1, vex_num):
    min_value=99999
    for j in range(vex_num):
      if flag_list[j]==False and dist[j]!='N':
        min_value=dist[j]
        k=j
    flag_list[k]=True
    for j in range(vex_num):
      if data_matrix[k][j]=='N':
        temp='N'
      else:
        temp=min_value+data_matrix[k][j]
      if flag_list[j]==False and temp!='N' and temp<dist[j]:
        dist[j]=temp
        prev[j]=k
  for i in range(vex_num):
    print '顶点'+str(start_node)+'到顶点'+str(i)+'最短距离是--->'+str(dist[i])
def main_test_func(vex_num=10):
  '''''
  主测试函数
  '''
  start_time=time.time()
  data_matrix=random_matrix_genetor(vex_num)
  dijkstra(data_matrix,0)
  end_time=time.time()
  return end_time-start_time
if __name__ == '__main__':
  data_matrix=[[0,2,3,'N'],[2,0,'N',5],[3,'N',0,9],['N',5,9,0]]
  dijkstra(data_matrix, 0)
  time_list=[]
  print '----------------------------10顶点测试-------------------------------------'
  time10=main_test_func(10)
  time_list.append(time10)
  print '----------------------------50顶点测试-------------------------------------'
  time50=main_test_func(50)
  time_list.append(time50)
  print '----------------------------100顶点测试-------------------------------------'
  time100=main_test_func(100)
  time_list.append(time100)
  print '---------------------------------时间消耗对比--------------------------------'
  for one_time in time_list:
    print one_time

结果如下：

顶点0到顶点0最短距离是--->0
顶点0到顶点1最短距离是--->2
顶点0到顶点2最短距离是--->3
顶点0到顶点3最短距离是--->12
----------------------------10顶点测试-------------------------------------
顶点0到顶点0最短距离是--->0
顶点0到顶点1最短距离是--->71
顶点0到顶点2最短距离是--->20
顶点0到顶点3最短距离是--->21
顶点0到顶点4最短距离是--->50
顶点0到顶点5最短距离是--->10
顶点0到顶点6最短距离是--->57
顶点0到顶点7最短距离是--->13
顶点0到顶点8最短距离是--->47
顶点0到顶点9最短距离是--->21
----------------------------50顶点测试-------------------------------------
顶点0到顶点0最短距离是--->0
顶点0到顶点1最短距离是--->6
顶点0到顶点2最短距离是--->6
顶点0到顶点3最短距离是--->4
顶点0到顶点4最短距离是--->24
顶点0到顶点5最短距离是--->13
顶点0到顶点6最短距离是--->15
顶点0到顶点7最短距离是--->14
顶点0到顶点8最短距离是--->14
顶点0到顶点9最短距离是--->6
顶点0到顶点10最短距离是--->11
顶点0到顶点11最短距离是--->15
顶点0到顶点12最短距离是--->6
顶点0到顶点13最短距离是--->10
顶点0到顶点14最短距离是--->8
顶点0到顶点15最短距离是--->8
顶点0到顶点16最短距离是--->8
顶点0到顶点17最短距离是--->6
顶点0到顶点18最短距离是--->7
顶点0到顶点19最短距离是--->19
顶点0到顶点20最短距离是--->29
顶点0到顶点21最短距离是--->10
顶点0到顶点22最短距离是--->18
顶点0到顶点23最短距离是--->10
顶点0到顶点24最短距离是--->20
顶点0到顶点25最短距离是--->3
顶点0到顶点26最短距离是--->18
顶点0到顶点27最短距离是--->13
顶点0到顶点28最短距离是--->25
顶点0到顶点29最短距离是--->9
顶点0到顶点30最短距离是--->25
顶点0到顶点31最短距离是--->32
顶点0到顶点32最短距离是--->22
顶点0到顶点33最短距离是--->2
顶点0到顶点34最短距离是--->18
顶点0到顶点35最短距离是--->26
顶点0到顶点36最短距离是--->7
顶点0到顶点37最短距离是--->19
顶点0到顶点38最短距离是--->31
顶点0到顶点39最短距离是--->50
顶点0到顶点40最短距离是--->44
顶点0到顶点41最短距离是--->3
顶点0到顶点42最短距离是--->34
顶点0到顶点43最短距离是--->5
顶点0到顶点44最短距离是--->22
顶点0到顶点45最短距离是--->38
顶点0到顶点46最短距离是--->64
顶点0到顶点47最短距离是--->24
顶点0到顶点48最短距离是--->62
顶点0到顶点49最短距离是--->20
----------------------------100顶点测试-------------------------------------
顶点0到顶点0最短距离是--->0
顶点0到顶点1最短距离是--->6
顶点0到顶点2最短距离是--->10
顶点0到顶点3最短距离是--->8
顶点0到顶点4最短距离是--->12
顶点0到顶点5最短距离是--->17
顶点0到顶点6最短距离是--->10
顶点0到顶点7最短距离是--->15
顶点0到顶点8最短距离是--->14
顶点0到顶点9最短距离是--->13
顶点0到顶点10最短距离是--->3
顶点0到顶点11最短距离是--->1
顶点0到顶点12最短距离是--->12
顶点0到顶点13最短距离是--->16
顶点0到顶点14最短距离是--->17
顶点0到顶点15最短距离是--->13
顶点0到顶点16最短距离是--->13
顶点0到顶点17最短距离是--->14
顶点0到顶点18最短距离是--->9
顶点0到顶点19最短距离是--->10
顶点0到顶点20最短距离是--->17
顶点0到顶点21最短距离是--->15
顶点0到顶点22最短距离是--->14
顶点0到顶点23最短距离是--->14
顶点0到顶点24最短距离是--->16
顶点0到顶点25最短距离是--->11
顶点0到顶点26最短距离是--->9
顶点0到顶点27最短距离是--->13
顶点0到顶点28最短距离是--->8
顶点0到顶点29最短距离是--->20
顶点0到顶点30最短距离是--->12
顶点0到顶点31最短距离是--->20
顶点0到顶点32最短距离是--->14
顶点0到顶点33最短距离是--->13
顶点0到顶点34最短距离是--->14
顶点0到顶点35最短距离是--->17
顶点0到顶点36最短距离是--->18
顶点0到顶点37最短距离是--->11
顶点0到顶点38最短距离是--->7
顶点0到顶点39最短距离是--->13
顶点0到顶点40最短距离是--->17
顶点0到顶点41最短距离是--->18
顶点0到顶点42最短距离是--->11
顶点0到顶点43最短距离是--->14
顶点0到顶点44最短距离是--->14
顶点0到顶点45最短距离是--->15
顶点0到顶点46最短距离是--->19
顶点0到顶点47最短距离是--->9
顶点0到顶点48最短距离是--->14
顶点0到顶点49最短距离是--->5
顶点0到顶点50最短距离是--->14
顶点0到顶点51最短距离是--->13
顶点0到顶点52最短距离是--->17
顶点0到顶点53最短距离是--->17
顶点0到顶点54最短距离是--->16
顶点0到顶点55最短距离是--->13
顶点0到顶点56最短距离是--->9
顶点0到顶点57最短距离是--->26
顶点0到顶点58最短距离是--->19
顶点0到顶点59最短距离是--->6
顶点0到顶点60最短距离是--->14
顶点0到顶点61最短距离是--->23
顶点0到顶点62最短距离是--->8
顶点0到顶点63最短距离是--->17
顶点0到顶点64最短距离是--->26
顶点0到顶点65最短距离是--->15
顶点0到顶点66最短距离是--->9
顶点0到顶点67最短距离是--->20
顶点0到顶点68最短距离是--->17
顶点0到顶点69最短距离是--->21
顶点0到顶点70最短距离是--->19
顶点0到顶点71最短距离是--->8
顶点0到顶点72最短距离是--->30
顶点0到顶点73最短距离是--->19
顶点0到顶点74最短距离是--->7
顶点0到顶点75最短距离是--->15
顶点0到顶点76最短距离是--->14
顶点0到顶点77最短距离是--->13
顶点0到顶点78最短距离是--->42
顶点0到顶点79最短距离是--->18
顶点0到顶点80最短距离是--->19
顶点0到顶点81最短距离是--->14
顶点0到顶点82最短距离是--->41
顶点0到顶点83最短距离是--->44
顶点0到顶点84最短距离是--->29
顶点0到顶点85最短距离是--->7
顶点0到顶点86最短距离是--->27
顶点0到顶点87最短距离是--->45
顶点0到顶点88最短距离是--->24
顶点0到顶点89最短距离是--->30
顶点0到顶点90最短距离是--->39
顶点0到顶点91最短距离是--->3
顶点0到顶点92最短距离是--->42
顶点0到顶点93最短距离是--->29
顶点0到顶点94最短距离是--->59
顶点0到顶点95最短距离是--->27
顶点0到顶点96最短距离是--->18
顶点0到顶点97最短距离是--->93
顶点0到顶点98最短距离是--->82
顶点0到顶点99最短距离是--->16

至于时间的消耗如下：

---------------------------------时间消耗对比--------------------------------
0.00032901763916
0.00534200668335
0.0202090740204

在1000节点的测试情况下结果为：

----------------------------1000顶点测试-------------------------------------
顶点0到顶点0最短距离是--->0
顶点0到顶点1最短距离是--->4
顶点0到顶点2最短距离是--->3
顶点0到顶点3最短距离是--->4
顶点0到顶点4最短距离是--->3
顶点0到顶点5最短距离是--->3
顶点0到顶点6最短距离是--->3
顶点0到顶点7最短距离是--->3
顶点0到顶点8最短距离是--->3
顶点0到顶点9最短距离是--->4
顶点0到顶点10最短距离是--->4
顶点0到顶点11最短距离是--->4
顶点0到顶点12最短距离是--->3
顶点0到顶点13最短距离是--->4
顶点0到顶点14最短距离是--->4
顶点0到顶点15最短距离是--->3
顶点0到顶点16最短距离是--->4
顶点0到顶点17最短距离是--->4
顶点0到顶点18最短距离是--->4
顶点0到顶点19最短距离是--->3
顶点0到顶点20最短距离是--->4
顶点0到顶点21最短距离是--->3
顶点0到顶点22最短距离是--->3
顶点0到顶点23最短距离是--->4
顶点0到顶点24最短距离是--->4
顶点0到顶点25最短距离是--->4
顶点0到顶点26最短距离是--->3
顶点0到顶点27最短距离是--->4
顶点0到顶点28最短距离是--->3
顶点0到顶点29最短距离是--->3
顶点0到顶点30最短距离是--->3
顶点0到顶点31最短距离是--->5
顶点0到顶点32最短距离是--->2
顶点0到顶点33最短距离是--->3
顶点0到顶点34最短距离是--->5
顶点0到顶点35最短距离是--->4
顶点0到顶点36最短距离是--->4
顶点0到顶点37最短距离是--->1
顶点0到顶点38最短距离是--->4
顶点0到顶点39最短距离是--->5
顶点0到顶点40最短距离是--->3
顶点0到顶点41最短距离是--->4
顶点0到顶点42最短距离是--->3
顶点0到顶点43最短距离是--->4
顶点0到顶点44最短距离是--->3
顶点0到顶点45最短距离是--->3
顶点0到顶点46最短距离是--->3
顶点0到顶点47最短距离是--->3
顶点0到顶点48最短距离是--->3
顶点0到顶点49最短距离是--->2
顶点0到顶点50最短距离是--->3
顶点0到顶点51最短距离是--->4
顶点0到顶点52最短距离是--->5
顶点0到顶点53最短距离是--->4
顶点0到顶点54最短距离是--->4
顶点0到顶点55最短距离是--->4
顶点0到顶点56最短距离是--->2
顶点0到顶点57最短距离是--->3
顶点0到顶点58最短距离是--->4
顶点0到顶点59最短距离是--->4
顶点0到顶点60最短距离是--->3
顶点0到顶点61最短距离是--->4
顶点0到顶点62最短距离是--->3
顶点0到顶点63最短距离是--->4
顶点0到顶点64最短距离是--->5
顶点0到顶点65最短距离是--->4
顶点0到顶点66最短距离是--->5
顶点0到顶点67最短距离是--->3
顶点0到顶点68最短距离是--->3
顶点0到顶点69最短距离是--->3
顶点0到顶点70最短距离是--->3
顶点0到顶点71最短距离是--->4
顶点0到顶点72最短距离是--->2
顶点0到顶点73最短距离是--->2
顶点0到顶点74最短距离是--->3
顶点0到顶点75最短距离是--->3
顶点0到顶点76最短距离是--->2
顶点0到顶点77最短距离是--->3
顶点0到顶点78最短距离是--->3
顶点0到顶点79最短距离是--->4
顶点0到顶点80最短距离是--->4
顶点0到顶点81最短距离是--->4
顶点0到顶点82最短距离是--->4
顶点0到顶点83最短距离是--->4
顶点0到顶点84最短距离是--->3
顶点0到顶点85最短距离是--->5
顶点0到顶点86最短距离是--->2
顶点0到顶点87最短距离是--->4
顶点0到顶点88最短距离是--->4
顶点0到顶点89最短距离是--->4
顶点0到顶点90最短距离是--->4
顶点0到顶点91最短距离是--->2
顶点0到顶点92最短距离是--->4
顶点0到顶点93最短距离是--->4
顶点0到顶点94最短距离是--->4
顶点0到顶点95最短距离是--->3
顶点0到顶点96最短距离是--->3
顶点0到顶点97最短距离是--->4
顶点0到顶点98最短距离是--->2
顶点0到顶点99最短距离是--->4
顶点0到顶点100最短距离是--->4
顶点0到顶点101最短距离是--->5
顶点0到顶点102最短距离是--->4
顶点0到顶点103最短距离是--->3
顶点0到顶点104最短距离是--->3
顶点0到顶点105最短距离是--->2
顶点0到顶点106最短距离是--->4
顶点0到顶点107最短距离是--->3
顶点0到顶点108最短距离是--->4
顶点0到顶点109最短距离是--->3
顶点0到顶点110最短距离是--->4
顶点0到顶点111最短距离是--->3
顶点0到顶点112最短距离是--->4
顶点0到顶点113最短距离是--->4
顶点0到顶点114最短距离是--->4
顶点0到顶点115最短距离是--->4
顶点0到顶点116最短距离是--->4
顶点0到顶点117最短距离是--->4
顶点0到顶点118最短距离是--->2
顶点0到顶点119最短距离是--->4
顶点0到顶点120最短距离是--->4
顶点0到顶点121最短距离是--->4
顶点0到顶点122最短距离是--->5
顶点0到顶点123最短距离是--->4
顶点0到顶点124最短距离是--->3
顶点0到顶点125最短距离是--->5
顶点0到顶点126最短距离是--->4
顶点0到顶点127最短距离是--->2
顶点0到顶点128最短距离是--->3
顶点0到顶点129最短距离是--->4
顶点0到顶点130最短距离是--->3
顶点0到顶点131最短距离是--->4
顶点0到顶点132最短距离是--->4
顶点0到顶点133最短距离是--->4
顶点0到顶点134最短距离是--->3
顶点0到顶点135最短距离是--->4
顶点0到顶点136最短距离是--->4
顶点0到顶点137最短距离是--->3
顶点0到顶点138最短距离是--->4
顶点0到顶点139最短距离是--->4
顶点0到顶点140最短距离是--->5
顶点0到顶点141最短距离是--->4
顶点0到顶点142最短距离是--->4
顶点0到顶点143最短距离是--->3
顶点0到顶点144最短距离是--->5
顶点0到顶点145最短距离是--->4
顶点0到顶点146最短距离是--->2
顶点0到顶点147最短距离是--->4
顶点0到顶点148最短距离是--->4
顶点0到顶点149最短距离是--->4
顶点0到顶点150最短距离是--->4
顶点0到顶点151最短距离是--->4
顶点0到顶点152最短距离是--->3
顶点0到顶点153最短距离是--->3
顶点0到顶点154最短距离是--->2
顶点0到顶点155最短距离是--->3
顶点0到顶点156最短距离是--->3
顶点0到顶点157最短距离是--->3
顶点0到顶点158最短距离是--->5
顶点0到顶点159最短距离是--->4
顶点0到顶点160最短距离是--->2
顶点0到顶点161最短距离是--->4
顶点0到顶点162最短距离是--->4
顶点0到顶点163最短距离是--->5
顶点0到顶点164最短距离是--->3
顶点0到顶点165最短距离是--->4
顶点0到顶点166最短距离是--->3
顶点0到顶点167最短距离是--->4
顶点0到顶点168最短距离是--->4
顶点0到顶点169最短距离是--->4
顶点0到顶点170最短距离是--->3
顶点0到顶点171最短距离是--->4
顶点0到顶点172最短距离是--->2
顶点0到顶点173最短距离是--->4
顶点0到顶点174最短距离是--->4
顶点0到顶点175最短距离是--->4
顶点0到顶点176最短距离是--->3
顶点0到顶点177最短距离是--->5
顶点0到顶点178最短距离是--->2
顶点0到顶点179最短距离是--->4
顶点0到顶点180最短距离是--->3
顶点0到顶点181最短距离是--->3
顶点0到顶点182最短距离是--->3
顶点0到顶点183最短距离是--->4
顶点0到顶点184最短距离是--->4
顶点0到顶点185最短距离是--->5
顶点0到顶点186最短距离是--->4
顶点0到顶点187最短距离是--->4
顶点0到顶点188最短距离是--->4
顶点0到顶点189最短距离是--->4
顶点0到顶点190最短距离是--->4
顶点0到顶点191最短距离是--->3
顶点0到顶点192最短距离是--->5
顶点0到顶点193最短距离是--->3
顶点0到顶点194最短距离是--->4
顶点0到顶点195最短距离是--->4
顶点0到顶点196最短距离是--->4
顶点0到顶点197最短距离是--->4
顶点0到顶点198最短距离是--->3
顶点0到顶点199最短距离是--->3
顶点0到顶点200最短距离是--->5
顶点0到顶点201最短距离是--->5
顶点0到顶点202最短距离是--->5
顶点0到顶点203最短距离是--->3
顶点0到顶点204最短距离是--->3
顶点0到顶点205最短距离是--->3
顶点0到顶点206最短距离是--->2
顶点0到顶点207最短距离是--->4
顶点0到顶点208最短距离是--->4
顶点0到顶点209最短距离是--->5
顶点0到顶点210最短距离是--->2
顶点0到顶点211最短距离是--->4
顶点0到顶点212最短距离是--->3
顶点0到顶点213最短距离是--->4
顶点0到顶点214最短距离是--->4
顶点0到顶点215最短距离是--->2
顶点0到顶点216最短距离是--->5
顶点0到顶点217最短距离是--->3
顶点0到顶点218最短距离是--->5
顶点0到顶点219最短距离是--->3
顶点0到顶点220最短距离是--->4
顶点0到顶点221最短距离是--->4
顶点0到顶点222最短距离是--->3
顶点0到顶点223最短距离是--->5
顶点0到顶点224最短距离是--->5
顶点0到顶点225最短距离是--->4
顶点0到顶点226最短距离是--->2
顶点0到顶点227最短距离是--->4
顶点0到顶点228最短距离是--->5
顶点0到顶点229最短距离是--->3
顶点0到顶点230最短距离是--->3
顶点0到顶点231最短距离是--->3
顶点0到顶点232最短距离是--->2
顶点0到顶点233最短距离是--->4
顶点0到顶点234最短距离是--->4
顶点0到顶点235最短距离是--->5
顶点0到顶点236最短距离是--->4
顶点0到顶点237最短距离是--->4
顶点0到顶点238最短距离是--->5
顶点0到顶点239最短距离是--->4
顶点0到顶点240最短距离是--->4
顶点0到顶点241最短距离是--->4
顶点0到顶点242最短距离是--->5
顶点0到顶点243最短距离是--->4
顶点0到顶点244最短距离是--->1
顶点0到顶点245最短距离是--->4
顶点0到顶点246最短距离是--->4
顶点0到顶点247最短距离是--->4
顶点0到顶点248最短距离是--->4
顶点0到顶点249最短距离是--->4
顶点0到顶点250最短距离是--->4
顶点0到顶点251最短距离是--->4
顶点0到顶点252最短距离是--->3
顶点0到顶点253最短距离是--->4
顶点0到顶点254最短距离是--->4
顶点0到顶点255最短距离是--->5
顶点0到顶点256最短距离是--->3
顶点0到顶点257最短距离是--->5
顶点0到顶点258最短距离是--->3
顶点0到顶点259最短距离是--->3
顶点0到顶点260最短距离是--->2
顶点0到顶点261最短距离是--->4
顶点0到顶点262最短距离是--->4
顶点0到顶点263最短距离是--->4
顶点0到顶点264最短距离是--->5
顶点0到顶点265最短距离是--->5
顶点0到顶点266最短距离是--->3
顶点0到顶点267最短距离是--->3
顶点0到顶点268最短距离是--->4
顶点0到顶点269最短距离是--->4
顶点0到顶点270最短距离是--->3
顶点0到顶点271最短距离是--->4
顶点0到顶点272最短距离是--->3
顶点0到顶点273最短距离是--->3
顶点0到顶点274最短距离是--->4
顶点0到顶点275最短距离是--->4
顶点0到顶点276最短距离是--->4
顶点0到顶点277最短距离是--->5
顶点0到顶点278最短距离是--->3
顶点0到顶点279最短距离是--->5
顶点0到顶点280最短距离是--->5
顶点0到顶点281最短距离是--->5
顶点0到顶点282最短距离是--->5
顶点0到顶点283最短距离是--->3
顶点0到顶点284最短距离是--->3
顶点0到顶点285最短距离是--->5
顶点0到顶点286最短距离是--->5
顶点0到顶点287最短距离是--->4
顶点0到顶点288最短距离是--->4
顶点0到顶点289最短距离是--->4
顶点0到顶点290最短距离是--->4
顶点0到顶点291最短距离是--->2
顶点0到顶点292最短距离是--->3
顶点0到顶点293最短距离是--->1
顶点0到顶点294最短距离是--->2
顶点0到顶点295最短距离是--->3
顶点0到顶点296最短距离是--->4
顶点0到顶点297最短距离是--->5
顶点0到顶点298最短距离是--->5
顶点0到顶点299最短距离是--->4
顶点0到顶点300最短距离是--->5
顶点0到顶点301最短距离是--->4
顶点0到顶点302最短距离是--->3
顶点0到顶点303最短距离是--->5
顶点0到顶点304最短距离是--->4
顶点0到顶点305最短距离是--->3
顶点0到顶点306最短距离是--->3
顶点0到顶点307最短距离是--->5
顶点0到顶点308最短距离是--->4
顶点0到顶点309最短距离是--->5
顶点0到顶点310最短距离是--->4
顶点0到顶点311最短距离是--->4
顶点0到顶点312最短距离是--->4
顶点0到顶点313最短距离是--->4
顶点0到顶点314最短距离是--->4
顶点0到顶点315最短距离是--->6
顶点0到顶点316最短距离是--->5
顶点0到顶点317最短距离是--->6
顶点0到顶点318最短距离是--->4
顶点0到顶点319最短距离是--->4
顶点0到顶点320最短距离是--->5
顶点0到顶点321最短距离是--->3
顶点0到顶点322最短距离是--->4
顶点0到顶点323最短距离是--->4
顶点0到顶点324最短距离是--->4
顶点0到顶点325最短距离是--->4
顶点0到顶点326最短距离是--->3
顶点0到顶点327最短距离是--->5
顶点0到顶点328最短距离是--->4
顶点0到顶点329最短距离是--->5
顶点0到顶点330最短距离是--->5
顶点0到顶点331最短距离是--->3
顶点0到顶点332最短距离是--->4
顶点0到顶点333最短距离是--->4
顶点0到顶点334最短距离是--->4
顶点0到顶点335最短距离是--->5
顶点0到顶点336最短距离是--->5
顶点0到顶点337最短距离是--->4
顶点0到顶点338最短距离是--->4
顶点0到顶点339最短距离是--->4
顶点0到顶点340最短距离是--->3
顶点0到顶点341最短距离是--->5
顶点0到顶点342最短距离是--->2
顶点0到顶点343最短距离是--->3
顶点0到顶点344最短距离是--->5
顶点0到顶点345最短距离是--->3
顶点0到顶点346最短距离是--->5
顶点0到顶点347最短距离是--->5
顶点0到顶点348最短距离是--->3
顶点0到顶点349最短距离是--->3
顶点0到顶点350最短距离是--->4
顶点0到顶点351最短距离是--->3
顶点0到顶点352最短距离是--->4
顶点0到顶点353最短距离是--->5
顶点0到顶点354最短距离是--->4
顶点0到顶点355最短距离是--->6
顶点0到顶点356最短距离是--->4
顶点0到顶点357最短距离是--->5
顶点0到顶点358最短距离是--->5
顶点0到顶点359最短距离是--->3
顶点0到顶点360最短距离是--->3
顶点0到顶点361最短距离是--->4
顶点0到顶点362最短距离是--->3
顶点0到顶点363最短距离是--->4
顶点0到顶点364最短距离是--->2
顶点0到顶点365最短距离是--->5
顶点0到顶点366最短距离是--->4
顶点0到顶点367最短距离是--->5
顶点0到顶点368最短距离是--->5
顶点0到顶点369最短距离是--->4
顶点0到顶点370最短距离是--->5
顶点0到顶点371最短距离是--->4
顶点0到顶点372最短距离是--->3
顶点0到顶点373最短距离是--->3
顶点0到顶点374最短距离是--->5
顶点0到顶点375最短距离是--->4
顶点0到顶点376最短距离是--->3
顶点0到顶点377最短距离是--->5
顶点0到顶点378最短距离是--->5
顶点0到顶点379最短距离是--->3
顶点0到顶点380最短距离是--->4
顶点0到顶点381最短距离是--->4
顶点0到顶点382最短距离是--->5
顶点0到顶点383最短距离是--->3
顶点0到顶点384最短距离是--->5
顶点0到顶点385最短距离是--->3
顶点0到顶点386最短距离是--->4
顶点0到顶点387最短距离是--->2
顶点0到顶点388最短距离是--->4
顶点0到顶点389最短距离是--->5
顶点0到顶点390最短距离是--->4
顶点0到顶点391最短距离是--->5
顶点0到顶点392最短距离是--->4
顶点0到顶点393最短距离是--->4
顶点0到顶点394最短距离是--->3
顶点0到顶点395最短距离是--->5
顶点0到顶点396最短距离是--->3
顶点0到顶点397最短距离是--->3
顶点0到顶点398最短距离是--->5
顶点0到顶点399最短距离是--->5
顶点0到顶点400最短距离是--->4
顶点0到顶点401最短距离是--->2
顶点0到顶点402最短距离是--->4
顶点0到顶点403最短距离是--->3
顶点0到顶点404最短距离是--->5
顶点0到顶点405最短距离是--->4
顶点0到顶点406最短距离是--->4
顶点0到顶点407最短距离是--->4
顶点0到顶点408最短距离是--->4
顶点0到顶点409最短距离是--->6
顶点0到顶点410最短距离是--->4
顶点0到顶点411最短距离是--->4
顶点0到顶点412最短距离是--->3
顶点0到顶点413最短距离是--->4
顶点0到顶点414最短距离是--->3
顶点0到顶点415最短距离是--->5
顶点0到顶点416最短距离是--->4
顶点0到顶点417最短距离是--->4
顶点0到顶点418最短距离是--->3
顶点0到顶点419最短距离是--->2
顶点0到顶点420最短距离是--->4
顶点0到顶点421最短距离是--->4
顶点0到顶点422最短距离是--->1
顶点0到顶点423最短距离是--->3
顶点0到顶点424最短距离是--->4
顶点0到顶点425最短距离是--->4
顶点0到顶点426最短距离是--->4
顶点0到顶点427最短距离是--->3
顶点0到顶点428最短距离是--->4
顶点0到顶点429最短距离是--->5
顶点0到顶点430最短距离是--->3
顶点0到顶点431最短距离是--->4
顶点0到顶点432最短距离是--->5
顶点0到顶点433最短距离是--->4
顶点0到顶点434最短距离是--->4
顶点0到顶点435最短距离是--->6
顶点0到顶点436最短距离是--->5
顶点0到顶点437最短距离是--->5
顶点0到顶点438最短距离是--->5
顶点0到顶点439最短距离是--->4
顶点0到顶点440最短距离是--->5
顶点0到顶点441最短距离是--->5
顶点0到顶点442最短距离是--->5
顶点0到顶点443最短距离是--->5
顶点0到顶点444最短距离是--->3
顶点0到顶点445最短距离是--->5
顶点0到顶点446最短距离是--->2
顶点0到顶点447最短距离是--->4
顶点0到顶点448最短距离是--->4
顶点0到顶点449最短距离是--->4
顶点0到顶点450最短距离是--->5
顶点0到顶点451最短距离是--->4
顶点0到顶点452最短距离是--->5
顶点0到顶点453最短距离是--->4
顶点0到顶点454最短距离是--->5
顶点0到顶点455最短距离是--->4
顶点0到顶点456最短距离是--->5
顶点0到顶点457最短距离是--->6
顶点0到顶点458最短距离是--->4
顶点0到顶点459最短距离是--->5
顶点0到顶点460最短距离是--->2
顶点0到顶点461最短距离是--->5
顶点0到顶点462最短距离是--->5
顶点0到顶点463最短距离是--->2
顶点0到顶点464最短距离是--->4
顶点0到顶点465最短距离是--->4
顶点0到顶点466最短距离是--->4
顶点0到顶点467最短距离是--->3
顶点0到顶点468最短距离是--->4
顶点0到顶点469最短距离是--->6
顶点0到顶点470最短距离是--->3
顶点0到顶点471最短距离是--->5
顶点0到顶点472最短距离是--->5
顶点0到顶点473最短距离是--->4
顶点0到顶点474最短距离是--->4
顶点0到顶点475最短距离是--->1
顶点0到顶点476最短距离是--->4
顶点0到顶点477最短距离是--->5
顶点0到顶点478最短距离是--->4
顶点0到顶点479最短距离是--->4
顶点0到顶点480最短距离是--->4
顶点0到顶点481最短距离是--->3
顶点0到顶点482最短距离是--->4
顶点0到顶点483最短距离是--->5
顶点0到顶点484最短距离是--->4
顶点0到顶点485最短距离是--->4
顶点0到顶点486最短距离是--->4
顶点0到顶点487最短距离是--->7
顶点0到顶点488最短距离是--->5
顶点0到顶点489最短距离是--->4
顶点0到顶点490最短距离是--->4
顶点0到顶点491最短距离是--->6
顶点0到顶点492最短距离是--->6
顶点0到顶点493最短距离是--->5
顶点0到顶点494最短距离是--->4
顶点0到顶点495最短距离是--->4
顶点0到顶点496最短距离是--->3
顶点0到顶点497最短距离是--->4
顶点0到顶点498最短距离是--->5
顶点0到顶点499最短距离是--->4
顶点0到顶点500最短距离是--->6
顶点0到顶点501最短距离是--->1
顶点0到顶点502最短距离是--->4
顶点0到顶点503最短距离是--->6
顶点0到顶点504最短距离是--->5
顶点0到顶点505最短距离是--->5
顶点0到顶点506最短距离是--->4
顶点0到顶点507最短距离是--->4
顶点0到顶点508最短距离是--->5
顶点0到顶点509最短距离是--->5
顶点0到顶点510最短距离是--->5
顶点0到顶点511最短距离是--->6
顶点0到顶点512最短距离是--->5
顶点0到顶点513最短距离是--->3
顶点0到顶点514最短距离是--->7
顶点0到顶点515最短距离是--->6
顶点0到顶点516最短距离是--->5
顶点0到顶点517最短距离是--->5
顶点0到顶点518最短距离是--->5
顶点0到顶点519最短距离是--->5
顶点0到顶点520最短距离是--->6
顶点0到顶点521最短距离是--->5
顶点0到顶点522最短距离是--->4
顶点0到顶点523最短距离是--->5
顶点0到顶点524最短距离是--->5
顶点0到顶点525最短距离是--->4
顶点0到顶点526最短距离是--->2
顶点0到顶点527最短距离是--->4
顶点0到顶点528最短距离是--->4
顶点0到顶点529最短距离是--->4
顶点0到顶点530最短距离是--->5
顶点0到顶点531最短距离是--->5
顶点0到顶点532最短距离是--->5
顶点0到顶点533最短距离是--->4
顶点0到顶点534最短距离是--->6
顶点0到顶点535最短距离是--->5
顶点0到顶点536最短距离是--->5
顶点0到顶点537最短距离是--->7
顶点0到顶点538最短距离是--->6
顶点0到顶点539最短距离是--->5
顶点0到顶点540最短距离是--->7
顶点0到顶点541最短距离是--->3
顶点0到顶点542最短距离是--->5
顶点0到顶点543最短距离是--->5
顶点0到顶点544最短距离是--->5
顶点0到顶点545最短距离是--->5
顶点0到顶点546最短距离是--->4
顶点0到顶点547最短距离是--->5
顶点0到顶点548最短距离是--->6
顶点0到顶点549最短距离是--->3
顶点0到顶点550最短距离是--->6
顶点0到顶点551最短距离是--->4
顶点0到顶点552最短距离是--->5
顶点0到顶点553最短距离是--->6
顶点0到顶点554最短距离是--->4
顶点0到顶点555最短距离是--->5
顶点0到顶点556最短距离是--->4
顶点0到顶点557最短距离是--->6
顶点0到顶点558最短距离是--->7
顶点0到顶点559最短距离是--->4
顶点0到顶点560最短距离是--->4
顶点0到顶点561最短距离是--->5
顶点0到顶点562最短距离是--->5
顶点0到顶点563最短距离是--->5
顶点0到顶点564最短距离是--->4
顶点0到顶点565最短距离是--->6
顶点0到顶点566最短距离是--->4
顶点0到顶点567最短距离是--->2
顶点0到顶点568最短距离是--->5
顶点0到顶点569最短距离是--->4
顶点0到顶点570最短距离是--->7
顶点0到顶点571最短距离是--->5
顶点0到顶点572最短距离是--->4
顶点0到顶点573最短距离是--->6
顶点0到顶点574最短距离是--->5
顶点0到顶点575最短距离是--->4
顶点0到顶点576最短距离是--->5
顶点0到顶点577最短距离是--->4
顶点0到顶点578最短距离是--->5
顶点0到顶点579最短距离是--->4
顶点0到顶点580最短距离是--->8
顶点0到顶点581最短距离是--->3
顶点0到顶点582最短距离是--->4
顶点0到顶点583最短距离是--->6
顶点0到顶点584最短距离是--->5
顶点0到顶点585最短距离是--->3
顶点0到顶点586最短距离是--->5
顶点0到顶点587最短距离是--->5
顶点0到顶点588最短距离是--->5
顶点0到顶点589最短距离是--->4
顶点0到顶点590最短距离是--->5
顶点0到顶点591最短距离是--->4
顶点0到顶点592最短距离是--->4
顶点0到顶点593最短距离是--->4
顶点0到顶点594最短距离是--->4
顶点0到顶点595最短距离是--->4
顶点0到顶点596最短距离是--->5
顶点0到顶点597最短距离是--->3
顶点0到顶点598最短距离是--->5
顶点0到顶点599最短距离是--->4
顶点0到顶点600最短距离是--->5
顶点0到顶点601最短距离是--->6
顶点0到顶点602最短距离是--->6
顶点0到顶点603最短距离是--->5
顶点0到顶点604最短距离是--->7
顶点0到顶点605最短距离是--->5
顶点0到顶点606最短距离是--->5
顶点0到顶点607最短距离是--->5
顶点0到顶点608最短距离是--->3
顶点0到顶点609最短距离是--->5
顶点0到顶点610最短距离是--->4
顶点0到顶点611最短距离是--->6
顶点0到顶点612最短距离是--->3
顶点0到顶点613最短距离是--->4
顶点0到顶点614最短距离是--->4
顶点0到顶点615最短距离是--->7
顶点0到顶点616最短距离是--->3
顶点0到顶点617最短距离是--->4
顶点0到顶点618最短距离是--->5
顶点0到顶点619最短距离是--->4
顶点0到顶点620最短距离是--->6
顶点0到顶点621最短距离是--->7
顶点0到顶点622最短距离是--->4
顶点0到顶点623最短距离是--->3
顶点0到顶点624最短距离是--->4
顶点0到顶点625最短距离是--->5
顶点0到顶点626最短距离是--->6
顶点0到顶点627最短距离是--->4
顶点0到顶点628最短距离是--->4
顶点0到顶点629最短距离是--->5
顶点0到顶点630最短距离是--->4
顶点0到顶点631最短距离是--->4
顶点0到顶点632最短距离是--->3
顶点0到顶点633最短距离是--->4
顶点0到顶点634最短距离是--->4
顶点0到顶点635最短距离是--->2
顶点0到顶点636最短距离是--->6
顶点0到顶点637最短距离是--->3
顶点0到顶点638最短距离是--->5
顶点0到顶点639最短距离是--->5
顶点0到顶点640最短距离是--->3
顶点0到顶点641最短距离是--->5
顶点0到顶点642最短距离是--->6
顶点0到顶点643最短距离是--->4
顶点0到顶点644最短距离是--->5
顶点0到顶点645最短距离是--->6
顶点0到顶点646最短距离是--->4
顶点0到顶点647最短距离是--->5
顶点0到顶点648最短距离是--->5
顶点0到顶点649最短距离是--->4
顶点0到顶点650最短距离是--->4
顶点0到顶点651最短距离是--->7
顶点0到顶点652最短距离是--->3
顶点0到顶点653最短距离是--->5
顶点0到顶点654最短距离是--->6
顶点0到顶点655最短距离是--->5
顶点0到顶点656最短距离是--->3
顶点0到顶点657最短距离是--->5
顶点0到顶点658最短距离是--->3
顶点0到顶点659最短距离是--->3
顶点0到顶点660最短距离是--->5
顶点0到顶点661最短距离是--->6
顶点0到顶点662最短距离是--->4
顶点0到顶点663最短距离是--->3
顶点0到顶点664最短距离是--->4
顶点0到顶点665最短距离是--->4
顶点0到顶点666最短距离是--->4
顶点0到顶点667最短距离是--->3
顶点0到顶点668最短距离是--->3
顶点0到顶点669最短距离是--->5
顶点0到顶点670最短距离是--->4
顶点0到顶点671最短距离是--->3
顶点0到顶点672最短距离是--->3
顶点0到顶点673最短距离是--->5
顶点0到顶点674最短距离是--->6
顶点0到顶点675最短距离是--->4
顶点0到顶点676最短距离是--->6
顶点0到顶点677最短距离是--->6
顶点0到顶点678最短距离是--->6
顶点0到顶点679最短距离是--->3
顶点0到顶点680最短距离是--->6
顶点0到顶点681最短距离是--->7
顶点0到顶点682最短距离是--->4
顶点0到顶点683最短距离是--->3
顶点0到顶点684最短距离是--->6
顶点0到顶点685最短距离是--->6
顶点0到顶点686最短距离是--->4
顶点0到顶点687最短距离是--->7
顶点0到顶点688最短距离是--->3
顶点0到顶点689最短距离是--->4
顶点0到顶点690最短距离是--->3
顶点0到顶点691最短距离是--->3
顶点0到顶点692最短距离是--->4
顶点0到顶点693最短距离是--->6
顶点0到顶点694最短距离是--->7
顶点0到顶点695最短距离是--->5
顶点0到顶点696最短距离是--->5
顶点0到顶点697最短距离是--->8
顶点0到顶点698最短距离是--->6
顶点0到顶点699最短距离是--->6
顶点0到顶点700最短距离是--->5
顶点0到顶点701最短距离是--->4
顶点0到顶点702最短距离是--->5
顶点0到顶点703最短距离是--->2
顶点0到顶点704最短距离是--->7
顶点0到顶点705最短距离是--->2
顶点0到顶点706最短距离是--->2
顶点0到顶点707最短距离是--->6
顶点0到顶点708最短距离是--->6
顶点0到顶点709最短距离是--->4
顶点0到顶点710最短距离是--->4
顶点0到顶点711最短距离是--->3
顶点0到顶点712最短距离是--->7
顶点0到顶点713最短距离是--->5
顶点0到顶点714最短距离是--->4
顶点0到顶点715最短距离是--->5
顶点0到顶点716最短距离是--->6
顶点0到顶点717最短距离是--->6
顶点0到顶点718最短距离是--->4
顶点0到顶点719最短距离是--->6
顶点0到顶点720最短距离是--->7
顶点0到顶点721最短距离是--->1
顶点0到顶点722最短距离是--->6
顶点0到顶点723最短距离是--->8
顶点0到顶点724最短距离是--->7
顶点0到顶点725最短距离是--->6
顶点0到顶点726最短距离是--->5
顶点0到顶点727最短距离是--->6
顶点0到顶点728最短距离是--->6
顶点0到顶点729最短距离是--->5
顶点0到顶点730最短距离是--->6
顶点0到顶点731最短距离是--->7
顶点0到顶点732最短距离是--->5
顶点0到顶点733最短距离是--->3
顶点0到顶点734最短距离是--->7
顶点0到顶点735最短距离是--->6
顶点0到顶点736最短距离是--->4
顶点0到顶点737最短距离是--->8
顶点0到顶点738最短距离是--->5
顶点0到顶点739最短距离是--->7
顶点0到顶点740最短距离是--->6
顶点0到顶点741最短距离是--->4
顶点0到顶点742最短距离是--->3
顶点0到顶点743最短距离是--->6
顶点0到顶点744最短距离是--->2
顶点0到顶点745最短距离是--->7
顶点0到顶点746最短距离是--->7
顶点0到顶点747最短距离是--->5
顶点0到顶点748最短距离是--->6
顶点0到顶点749最短距离是--->4
顶点0到顶点750最短距离是--->6
顶点0到顶点751最短距离是--->7
顶点0到顶点752最短距离是--->6
顶点0到顶点753最短距离是--->6
顶点0到顶点754最短距离是--->3
顶点0到顶点755最短距离是--->6
顶点0到顶点756最短距离是--->10
顶点0到顶点757最短距离是--->5
顶点0到顶点758最短距离是--->6
顶点0到顶点759最短距离是--->4
顶点0到顶点760最短距离是--->3
顶点0到顶点761最短距离是--->7
顶点0到顶点762最短距离是--->5
顶点0到顶点763最短距离是--->7
顶点0到顶点764最短距离是--->5
顶点0到顶点765最短距离是--->6
顶点0到顶点766最短距离是--->7
顶点0到顶点767最短距离是--->6
顶点0到顶点768最短距离是--->4
顶点0到顶点769最短距离是--->7
顶点0到顶点770最短距离是--->6
顶点0到顶点771最短距离是--->3
顶点0到顶点772最短距离是--->8
顶点0到顶点773最短距离是--->1
顶点0到顶点774最短距离是--->7
顶点0到顶点775最短距离是--->8
顶点0到顶点776最短距离是--->6
顶点0到顶点777最短距离是--->6
顶点0到顶点778最短距离是--->6
顶点0到顶点779最短距离是--->3
顶点0到顶点780最短距离是--->8
顶点0到顶点781最短距离是--->4
顶点0到顶点782最短距离是--->5
顶点0到顶点783最短距离是--->6
顶点0到顶点784最短距离是--->6
顶点0到顶点785最短距离是--->6
顶点0到顶点786最短距离是--->6
顶点0到顶点787最短距离是--->6
顶点0到顶点788最短距离是--->8
顶点0到顶点789最短距离是--->6
顶点0到顶点790最短距离是--->8
顶点0到顶点791最短距离是--->6
顶点0到顶点792最短距离是--->8
顶点0到顶点793最短距离是--->10
顶点0到顶点794最短距离是--->7
顶点0到顶点795最短距离是--->7
顶点0到顶点796最短距离是--->8
顶点0到顶点797最短距离是--->6
顶点0到顶点798最短距离是--->8
顶点0到顶点799最短距离是--->8
顶点0到顶点800最短距离是--->5
顶点0到顶点801最短距离是--->8
顶点0到顶点802最短距离是--->7
顶点0到顶点803最短距离是--->4
顶点0到顶点804最短距离是--->5
顶点0到顶点805最短距离是--->5
顶点0到顶点806最短距离是--->8
顶点0到顶点807最短距离是--->8
顶点0到顶点808最短距离是--->11
顶点0到顶点809最短距离是--->5
顶点0到顶点810最短距离是--->9
顶点0到顶点811最短距离是--->2
顶点0到顶点812最短距离是--->10
顶点0到顶点813最短距离是--->12
顶点0到顶点814最短距离是--->7
顶点0到顶点815最短距离是--->4
顶点0到顶点816最短距离是--->6
顶点0到顶点817最短距离是--->5
顶点0到顶点818最短距离是--->6
顶点0到顶点819最短距离是--->6
顶点0到顶点820最短距离是--->9
顶点0到顶点821最短距离是--->4
顶点0到顶点822最短距离是--->3
顶点0到顶点823最短距离是--->7
顶点0到顶点824最短距离是--->7
顶点0到顶点825最短距离是--->11
顶点0到顶点826最短距离是--->7
顶点0到顶点827最短距离是--->11
顶点0到顶点828最短距离是--->5
顶点0到顶点829最短距离是--->8
顶点0到顶点830最短距离是--->8
顶点0到顶点831最短距离是--->3
顶点0到顶点832最短距离是--->4
顶点0到顶点833最短距离是--->9
顶点0到顶点834最短距离是--->8
顶点0到顶点835最短距离是--->7
顶点0到顶点836最短距离是--->8
顶点0到顶点837最短距离是--->5
顶点0到顶点838最短距离是--->6
顶点0到顶点839最短距离是--->10
顶点0到顶点840最短距离是--->8
顶点0到顶点841最短距离是--->10
顶点0到顶点842最短距离是--->9
顶点0到顶点843最短距离是--->7
顶点0到顶点844最短距离是--->8
顶点0到顶点845最短距离是--->5
顶点0到顶点846最短距离是--->7
顶点0到顶点847最短距离是--->8
顶点0到顶点848最短距离是--->6
顶点0到顶点849最短距离是--->6
顶点0到顶点850最短距离是--->5
顶点0到顶点851最短距离是--->12
顶点0到顶点852最短距离是--->5
顶点0到顶点853最短距离是--->14
顶点0到顶点854最短距离是--->6
顶点0到顶点855最短距离是--->4
顶点0到顶点856最短距离是--->8
顶点0到顶点857最短距离是--->7
顶点0到顶点858最短距离是--->7
顶点0到顶点859最短距离是--->7
顶点0到顶点860最短距离是--->10
顶点0到顶点861最短距离是--->9
顶点0到顶点862最短距离是--->9
顶点0到顶点863最短距离是--->9
顶点0到顶点864最短距离是--->11
顶点0到顶点865最短距离是--->8
顶点0到顶点866最短距离是--->8
顶点0到顶点867最短距离是--->5
顶点0到顶点868最短距离是--->5
顶点0到顶点869最短距离是--->7
顶点0到顶点870最短距离是--->9
顶点0到顶点871最短距离是--->11
顶点0到顶点872最短距离是--->10
顶点0到顶点873最短距离是--->4
顶点0到顶点874最短距离是--->10
顶点0到顶点875最短距离是--->5
顶点0到顶点876最短距离是--->10
顶点0到顶点877最短距离是--->3
顶点0到顶点878最短距离是--->9
顶点0到顶点879最短距离是--->8
顶点0到顶点880最短距离是--->11
顶点0到顶点881最短距离是--->16
顶点0到顶点882最短距离是--->6
顶点0到顶点883最短距离是--->6
顶点0到顶点884最短距离是--->4
顶点0到顶点885最短距离是--->4
顶点0到顶点886最短距离是--->9
顶点0到顶点887最短距离是--->3
顶点0到顶点888最短距离是--->7
顶点0到顶点889最短距离是--->7
顶点0到顶点890最短距离是--->10
顶点0到顶点891最短距离是--->8
顶点0到顶点892最短距离是--->8
顶点0到顶点893最短距离是--->10
顶点0到顶点894最短距离是--->9
顶点0到顶点895最短距离是--->9
顶点0到顶点896最短距离是--->5
顶点0到顶点897最短距离是--->7
顶点0到顶点898最短距离是--->11
顶点0到顶点899最短距离是--->13
顶点0到顶点900最短距离是--->8
顶点0到顶点901最短距离是--->9
顶点0到顶点902最短距离是--->10
顶点0到顶点903最短距离是--->11
顶点0到顶点904最短距离是--->9
顶点0到顶点905最短距离是--->10
顶点0到顶点906最短距离是--->7
顶点0到顶点907最短距离是--->5
顶点0到顶点908最短距离是--->12
顶点0到顶点909最短距离是--->8
顶点0到顶点910最短距离是--->8
顶点0到顶点911最短距离是--->11
顶点0到顶点912最短距离是--->7
顶点0到顶点913最短距离是--->9
顶点0到顶点914最短距离是--->6
顶点0到顶点915最短距离是--->6
顶点0到顶点916最短距离是--->8
顶点0到顶点917最短距离是--->3
顶点0到顶点918最短距离是--->9
顶点0到顶点919最短距离是--->9
顶点0到顶点920最短距离是--->5
顶点0到顶点921最短距离是--->7
顶点0到顶点922最短距离是--->8
顶点0到顶点923最短距离是--->9
顶点0到顶点924最短距离是--->5
顶点0到顶点925最短距离是--->4
顶点0到顶点926最短距离是--->10
顶点0到顶点927最短距离是--->4
顶点0到顶点928最短距离是--->8
顶点0到顶点929最短距离是--->11
顶点0到顶点930最短距离是--->10
顶点0到顶点931最短距离是--->11
顶点0到顶点932最短距离是--->11
顶点0到顶点933最短距离是--->11
顶点0到顶点934最短距离是--->10
顶点0到顶点935最短距离是--->11
顶点0到顶点936最短距离是--->11
顶点0到顶点937最短距离是--->4
顶点0到顶点938最短距离是--->8
顶点0到顶点939最短距离是--->10
顶点0到顶点940最短距离是--->14
顶点0到顶点941最短距离是--->4
顶点0到顶点942最短距离是--->17
顶点0到顶点943最短距离是--->15
顶点0到顶点944最短距离是--->10
顶点0到顶点945最短距离是--->11
顶点0到顶点946最短距离是--->2
顶点0到顶点947最短距离是--->7
顶点0到顶点948最短距离是--->7
顶点0到顶点949最短距离是--->12
顶点0到顶点950最短距离是--->9
顶点0到顶点951最短距离是--->4
顶点0到顶点952最短距离是--->7
顶点0到顶点953最短距离是--->12
顶点0到顶点954最短距离是--->12
顶点0到顶点955最短距离是--->18
顶点0到顶点956最短距离是--->8
顶点0到顶点957最短距离是--->15
顶点0到顶点958最短距离是--->3
顶点0到顶点959最短距离是--->6
顶点0到顶点960最短距离是--->6
顶点0到顶点961最短距离是--->2
顶点0到顶点962最短距离是--->17
顶点0到顶点963最短距离是--->29
顶点0到顶点964最短距离是--->9
顶点0到顶点965最短距离是--->10
顶点0到顶点966最短距离是--->18
顶点0到顶点967最短距离是--->13
顶点0到顶点968最短距离是--->16
顶点0到顶点969最短距离是--->9
顶点0到顶点970最短距离是--->11
顶点0到顶点971最短距离是--->14
顶点0到顶点972最短距离是--->15
顶点0到顶点973最短距离是--->19
顶点0到顶点974最短距离是--->10
顶点0到顶点975最短距离是--->12
顶点0到顶点976最短距离是--->11
顶点0到顶点977最短距离是--->10
顶点0到顶点978最短距离是--->11
顶点0到顶点979最短距离是--->15
顶点0到顶点980最短距离是--->37
顶点0到顶点981最短距离是--->28
顶点0到顶点982最短距离是--->15
顶点0到顶点983最短距离是--->7
顶点0到顶点984最短距离是--->8
顶点0到顶点985最短距离是--->16
顶点0到顶点986最短距离是--->24
顶点0到顶点987最短距离是--->14
顶点0到顶点988最短距离是--->28
顶点0到顶点989最短距离是--->7
顶点0到顶点990最短距离是--->30
顶点0到顶点991最短距离是--->28
顶点0到顶点992最短距离是--->4
顶点0到顶点993最短距离是--->38
顶点0到顶点994最短距离是--->72
顶点0到顶点995最短距离是--->50
顶点0到顶点996最短距离是--->8
顶点0到顶点997最短距离是--->13
顶点0到顶点998最短距离是--->41
顶点0到顶点999最短距离是--->42
---------------------------------时间消耗对比--------------------------------
0.000325918197632
0.00543880462646
0.0203928947449
1.92220687866

可以发现：

Dijkstra算法在应对数据规模量级的增大的情况下表现出来的性能是很优越的，这也是在面对大规模图结构的时候不能使用Floyd算法的原因。

好了，关于 DIjkstra就说到这里了，如有问题欢迎讨论学习！

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python数学运算技巧总结》

希望本文所述对大家Python程序设计有所帮助。