What will be the correct code for given problem statement?

given an unrooted unweighted tree of n nodes and set of nodes that are compulsory to visit, we have to travel through tree starting from 1st node, visiting all the compulsory nodes and end at last node (as 5th node in above example is last node).Among all such paths, find the minimum length path and return the length of this path. Given an unrooted unweighted tree of n nodes, and an array visitNodes[] of length m, find the minimum length of the path from node 1 to node n such that it visits all the nodes among visitNodes (in any order) at least once.
Thus, the path must follow the given conditions:

• The path starts at node 1.

• The path ends at node n.

• The path can visit each node any number of times.

• Each node in visitNodes must be visited at least once in the path.

• From a current node, it is possible to travel to an adjacent node.
for example:
edges = {{1, 2}, {1, 3}, {3,4}, {3,5}}
visitNodes = [2, 4]
Output: 6

I tried to apply dijkstra’s algorithm but getting wrong output.

>Solution :

from collections import defaultdict, deque
from itertools import permutations
import heapq


def dijkstra_shortest_distance(start, graph):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor in graph[current_node]:
            distance = current_distance + 1  # +1 because it's unweighted
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances


def min_path_length(edges, visitNodes):
    # Convert edges to an adjacency list
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    # Calculate shortest paths between all pairs in visitNodes including node 1 and node n
    nodes_to_consider = [1] + visitNodes + [len(graph)]
    shortest_paths = defaultdict(dict)
    for node in nodes_to_consider:
        distances = dijkstra_shortest_distance(node, graph)
        for target in nodes_to_consider:
            shortest_paths[node][target] = distances[target]

    min_distance = float('inf')

    # Iterate through all permutations of visitNodes
    for perm in permutations(visitNodes):
        curr_distance = 0
        curr_node = 1
        for node in perm:
            curr_distance += shortest_paths[curr_node][node]
            curr_node = node
        curr_distance += shortest_paths[curr_node][len(graph)]
        min_distance = min(min_distance, curr_distance)

    return min_distance


edges = [(1, 2), (1, 3), (3, 4), (3, 5)]
visitNodes = [2, 4]
print(min_path_length(edges, visitNodes))  # Output: 6

I think this should work.