Untitled

mail@pastecode.io avatar
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))