djikstra
unknown
python
4 months ago
1.7 kB
1
Indexable
def dijkstra(graph, start, goal): # Initialise infinity = float("inf") distance = { } previous_vertex = { } shortest_path = [ ] # Set the shortest distance from the start for all vertices to infinity for vertex in graph : distance[vertex] = infinity # Set the shortest distance from the start for the start vertex to 0 distance[start] = 0 # Loop until all the vertices have been visited while graph: # Find the vertex with the shortest distance from the start shortest = None for vertex in graph: if shortest == None: shortest = vertex elif distance[vertex] < distance[shortest] : shortest = vertex # Calculate shortest distance for each edge for neighbour, cost in graph[shortest].items(): # Update the shortest distance for the vertex if the new value is lower if neighbour in graph and cost + distance[shortest] < distance[neighbour]: distance[neighbour] = cost + distance[shortest] previous_vertex[neighbour] = shortest # The vertex has now been visited, remove it from the vertices to consider graph.pop (shortest) #Generate the shortest path #Start from the goal, adding vertices to the front of the list vertex = goal while vertex != start: shortest_path.insert(0,vertex) vertex = previous_vertex[vertex] # Add the start vertex shortest_path.insert(0,start) # Return the shortest shortest_path return shortest_path graph={"A":{"B":4,"C":3,"D":2},"B":{"A":4,"E":4},"C":{"A":3,"D":1},"D":{"A":2,"C":1,"F":2},"E":{"B":4,"G":2},"F":{"D":2,"G":5},"G":{"E":2,"F":5}} print(dijkstra(graph, "A", "G"))
Editor is loading...
Leave a Comment