1

Hi im wroking on dijkstra's algorithm and the first hint in the comments is, '''For all the nodes in the graph, set distance equal to infinity and previous equal to none ''' What does he mean by this how do you set the values equal to infinity?Also in the method there is not end so im guessing just to make the end the adjacent node ? Im saying this because there is a are_adjacent method This is the little i have

def are_adjacent(self, value1, value2):
    return(self.find(value1).is_adjacent(self.find(value2)))


def dijkstra(self, start):
K..
  • 83
  • 1
  • 7

4 Answers4

0

You can do like this in Python:

var = float('inf')
var = float('-inf')   # for minus oo

With python >= 3.5 using the math module: (as @alpert and @YOU pointed out in the comments)

import math
var = math.inf
var = -math.inf
Reblochon Masque
  • 35,405
  • 10
  • 55
  • 80
0

You can set a value as infinite:

value = float('inf')

Or in python 3.5:

import math
value = math.inf
alpert
  • 4,500
  • 1
  • 17
  • 27
0
  1. You can set it to some big value something like 1e9 (NodeCount * MaximumEdgeWeight, there will be no path more than such value);
    1. Or set it to value "-1" and check it with some "if": if(d[v] == -1) {/* Then it is infinity */}.
107th
  • 19
  • 1
  • 4
-1

you can have the dictionary to have all the nodes in the graph as keys and their respective known distances as values, which you will keep on updating and will return it eventually E.g. {'A':0, 'B':3, 'C':5, 'D': 7}

Now, coming on your question that how to set distance to infinity as indeed the distance to all other nodes from the source is unknown initially, therefore set the initial distance to infinity. The following code would do the trick:

result = {}
result[source] = 0 # as the Distance from source to source itself is 0                
    
for node in graph.nodes:
   if (node != source):
       result[node] = sys.maxsize
mudassir ahmed
  • 191
  • 1
  • 1
  • 13
  • `sys.maxsize` is typically `2**63 - 1`, which is not infinity. This question already has plenty of correct answers. https://docs.python.org/3/library/sys.html#sys.maxsize – kaya3 Feb 26 '22 at 19:50
  • I have implemented the Dijkstra algorithm with this logic and it's working fine as sys.maxsize gives you a large enough number to be worked as infinity, therefore folks working on python<3.5 could make use of this working code – mudassir ahmed Feb 28 '22 at 07:24
  • Your answer says *"set the initial distance to infinity. The following code would do the trick:"* with no acknowledgement that the number you are setting it to is **not** infinity. Both integers and floating point values in Python can far exceed `sys.maxsize`, so this is not a general-purpose solution to the problem, and even so, there is no benefit of using `sys.maxsize` instead of explicitly writing `2 ** 63 - 1`. But still, there is no need to use a number that is not infinity, because infinity is a standard floating point number that can be used in any version of Python. – kaya3 Feb 28 '22 at 07:39
  • what do you think math.inf or float(inf) doing under the hood? – mudassir ahmed Mar 01 '22 at 08:15
  • It is the floating point number infinity. – kaya3 Mar 01 '22 at 08:37