zoobad.blogg.se

If B was previously marked with a distance greater than 8 then change it to 8. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. We do it using tuple pair, (distance, v)įor the current node, consider all of its unvisited neighbors and calculate their tentative distances. Create a list of the unvisited nodes called the unvisited list consisting of all the nodes. This is also done in the Vertex constructor: Actually, initialization is done in the Vertex constructor:įor the starting node, initialization is done in dijkstra() Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.Not updated : current = d next = e new_dist = 20 Updated : current = f next = e new_dist = 20 Updated : current = c next = f new_dist = 11 Updated : current = c next = d new_dist = 20 Not updated : current = b next = c new_dist = 9 Updated : current = b next = d new_dist = 22 Updated : current = a next = b new_dist = 7 Updated : current = a next = c new_dist = 9 Updated : current = a next = f new_dist = 14 Put all vertices not visited into the queue Print 'not updated : current = %s next = %s new_dist = %s' \ %(current.get_id(), next.get_id(), next.get_distance()) Print 'updated : current = %s next = %s new_dist = %s' \ New_dist = current.get_distance() + current.get_weight(next)

# Pops a vertex with the smallest distance # Set the distance for the start node to zero ''' make shortest path from v.previous''' Self.vert_dict.add_neighbor(self.vert_dict, cost) Self.num_vertices = self.num_vertices + 1 Return str(self.id) + ' adjacent: ' + str() The shortest() function constructs the shortest path starting from the target ('e') using predecessors.ĭef add_neighbor(self, neighbor, weight=0): The function dijkstra() calculates the shortest path. The source file is Dijkstra_shortest_path.py. In the code, we create two classes: Graph, which holds the master list of vertices, and Vertex, which represents each vertex in the graph (see Graph data structure).