Untitled
unknown
plain_text
a year ago
1.5 kB
2
Indexable
Never
// Initialize an empty queue and dictionary queue = empty visited = {P: 0} // Add P to the queue with distance 0 queue.push((P, 0)) // While the queue is not empty while queue is not empty: // Remove the junction with smallest distance from P current, distance = queue.pop() // Mark current as visited visited[current] = distance // If G has been visited, reconstruct the shortest path and return it if current == G: path = [G] while path[-1] != P: for neighbor in neighbors[path[-1]]: if neighbor in visited and visited[neighbor] == visited[path[-1]] - 1: path.append(neighbor) break path.reverse() return path // Find the unvisited neighbors of current and sort them in alphabetical order unvisited_neighbors = sorted([neighbor for neighbor in neighbors[current] if neighbor not in visited]) // For each unvisited neighbor of current for neighbor in unvisited_neighbors: // Calculate the distance from P to neighbor through current new_distance = distance + pathway_length(current, neighbor) // Update the dictionary if the new distance is shorter if neighbor not in visited or new_distance < visited[neighbor]: visited[neighbor] = new_distance // Add neighbor to the queue with the new distance queue.push((neighbor, new_distance))