I was working with this Dijkstra algorithm to find the shortest path.

For example :

direct way from a to b :5

direct way from b to c :2

direct way from a to c :9 ...then the shortest way from a to c would have a distance from 7, not 9.

the problem is: I thought I was adding numbers like 3.1, 2, 5.4, 6.7, 10.8, so numbers with only one digit after the decimal point, or natural numbers. but the result I got from this algorithm was like: 22.400000000000002.. and I have no idea why this happened.

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

and the following is the '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}
}

..and ''index' is...

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]))

Thanks!

CodePudding user response：

I am pretty sure it was answered numerous times, but I can't find it right now. Please, feel free to mark as a duplicate.

TLDR: there's nothing wrong with the algorithm, it's just because of how floating point numbers are represented in computer memory.

Computers store numbers in binary, including floating point numbers. Some fractions cannot be represented in binary, given the limited number of digits they're stored in. This sometimes leads to weird rounding errors like this (taken from this question):

n = 5.59
round(n, 1) # 5.5999999999999996

Note that this is also platform-dependent. Different CPUs and different Python implementations use different length to store floats. You might not see the same result on a different machine, or even on the same machine using different float types (e.g. through numpy)