疯狂的输出数字 - python 中的 Dijkstra 算法 - 寻找最短路径

Question

我正在使用 Dijkstra 算法寻找最短路径。

例如：

从 a 到 b 的直接方式 :5

从 b 到 c 的直接方式 :2

从a到c的直接方式:9 ...那么从 a 到 c 的最短路径距离 7，而不是 9。

问题是：我以为我在加数字，比如 3.1、2、5.4、6.7、10.8，所以小数点后只有一位的数字，或者自然数。但我从这个算法得到的结果是这样的： 22.400000000000002.. 我不知道为什么会这样。

import heapq  #you don't have to install this

def dijkstra(graph, start):
  distances = {node: float('inf') for node in graph}  
  distances[start] = 0  
  queue = []
  heapq.heappush(queue, [distances[start], start])  

  while queue:  
    current_distance, current_destination = heapq.heappop(queue)  

    if distances[current_destination] < current_distance:  
      continue
    
    for new_destination, new_distance in graph[current_destination].items():
      distance = current_distance + new_distance  
      if distance < distances[new_destination]: 
        distances[new_destination] = distance
        heapq.heappush(queue, [distance, new_destination]) 
    
  return distances

下面是'graph'

graph = {
    index[1]: {index[2]: 5.3, index[22]: 11.3},
    index[2]: {index[3]:4.7},
    index[3]: {index[4]: 4.1, index[8]: 9.4, index[22]:4.3},
    index[4]: {index[5]: 2.5, index[8]: 4.6},
    index[5]: {index[6]: 4.6, index[10]:7.5, index[16]:10.3,index[22]:5.8},
    index[6]: {index[7]: 5.8},
    index[7] : {index[8]:6.7},
    index[8] : {index[9]:5.1},
    index[9] : {index[10]:3.7},
    index[10] : {index[11]:5.2,index[17]:17.5},
    index[11] : {index[12]:8.7,index[13]:6.7, index[22]:11.2},
    index[12] : {index[13]:4.3,index[16]:15.9},
    index[13] : {index[14]:3.3,index[15]:6.5},
    index[14] : {index[15]:9.7,index[16]:10.1},
    index[15] : {index[16]:2.9},
    index[16] : {index[17]:7.1,index[18]:2.4,index[22]:4.2},
    index[17] : {index[18]:4.7},
    index[18] : {index[19]:9,index[21]:3.2},
    index[19] : {index[20]:4.2},
    index[20] : {index[21]:4.2},
    index[21] : {index[22]:1.7},
    index[22] : {index[1]:11.3}
}

..并且''index'是...

index = {
    1:'a',
    2:'b',
    3:'c',
    4:'d',
    5:'e',
    6:'f',
    7:'g',
    8:'h',
    9:'i',
    10:'j',
    11:'k',
    12:'l',
    13:'m',
    14:'n',
    15:'o',
    16:'p',
    17:'q',
    18:'r',
    19:'s',
    20:'t',
    21:'u',
    22:'v'
}

print('from',index[5],'to',dijkstra(graph, index[5]))

谢谢！

Answer 1

我很确定它已被多次回答，但我现在找不到。请随时标记为重复。

TLDR：算法没有问题，只是因为浮点数在计算机内存中的表示方式。

计算机以二进制形式存储数字，包括浮点数。有些分数不能用二进制表示，因为它们存储的位数有限。这有时会导致奇怪的舍入错误，如下所示（取自 this question）：

n = 5.59
round(n, 1) # 5.5999999999999996

请注意，这也取决于平台。不同的 CPU 和不同的 Python 实现使用不同的长度来存储浮点数。您可能不会在不同的机器上看到相同的结果，甚至在使用不同浮点类型的同一台机器上（例如通过 numpy）

疯狂的输出数字 - python 中的 Dijkstra 算法 - 寻找最短路径

crazy output numbers - Dijkstra algorithm in python - finding the shortest path

python

algorithm

math

graph-theory

dijkstra