Shortest path from s to t using python

[nkiki]

(V, E) be a graph and two vertices s and t. B ⊆ V be some set of vertices. How many vertices of the set B can there be at maximum on a shortest path from s to t? there may be several such paths. finding answer using python

code doesn't handle scenarios for multiple shortest paths from s to t. only considering first path found and returns the count for that path. code increments the count for vertices in set B inside the loop for neighbors. counting should be done only when the neighbor is in B and has not been visited before.

    def max_vertices_in_shortest_path(G, s, t, B):
        V, E = G
        # Initialize the count array with all elements set to -1
        count = [-1 for _ in range(len(V))]
        # Initialize the queue with the starting vertex
        queue = [s]
        # Mark the starting vertex as visited
        count[s] = 0

        while queue:
            current = queue.pop(0)
            for neighbor in E[current]:
                if count[neighbor] == -1:
                    count[neighbor] = count[current]
                    if neighbor in B:
                        count[neighbor] += 1
                    queue.append(neighbor)

        return count[t]

# Example usage:
V = [0, 1, 2, 3, 4, 5]
E = {0: [1, 2], 1: [3], 2: [3], 3: [4, 5], 4: [5], 5: []}
G = (V, E)
s = 0
t = 5
B = {1, 2, 4}

result = max_vertices_in_shortest_path(G, s, t, B)
print(result)

[Pedroski55]

Explain some more, a picture says a thousand words!

Maybe some examples for the various variables would clarify matters somewhat!

[nkiki]

(V, E) be a graph and two vertices s and t. B ⊆ V be some set of vertices. How many vertices of the set B can there be at maximum on a shortest path from s to t? there may be several such paths. finding answer using python

code doesn't handle scenarios for multiple shortest paths from s to t. only considering first path found and returns the count for that path. code increments the count for vertices in set B inside the loop for neighbors. counting should be done only when the neighbor is in B and has not been visited before

def max_vertices_in_shortest_path(G, s, t, B):
    V, E = G
    # Initialize the count array with all elements set to -1
    count = [-1 for _ in range(len(V))]
    # Initialize the queue with the starting vertex
    queue = [s]
    # Mark the starting vertex as visited
    count[s] = 0

    while queue:
        current = queue.pop(0)
        for neighbor in E[current]:
            if count[neighbor] == -1:
                count[neighbor] = count[current]
                if neighbor in B:
                    count[neighbor] += 1
                queue.append(neighbor)

    return count[t]

# Example usage:
V = [0, 1, 2, 3, 4, 5]
E = {0: [1, 2], 1: [3], 2: [3], 3: [4, 5], 4: [5], 5: []}
G = (V, E)
s = 0
t = 5
B = {1, 2, 4}

result = max_vertices_in_shortest_path(G, s, t, B)
print(result)

[deanhystad]

You need to find all possible paths, get the shortest path, report all paths that are that length. I think recursion would be a good choice for this problem. A recursive solution would start at t, pick a neighboring node, add the node to the path and call itself using the neighboring node as the start. When the search function picks a neighbor that is t, add the path to the list of paths, unwind to the previous recursion and pick the next neighbor. Your function should only allow moving to neighboring nodes that are not in the current path. You might also want to keep track of the shortest path. If a path exceeds the shortest path, there is no reason continuing along that path.

[Gribouillis]

I think you could also find the shortest path from s to t in a graph where the edges are weighted. If you give the weight 1 to edge a -> b when b is not in B and weight 1 - x if b is in B, where x = 1 / (1 + len(B)).

I think a shortest path in this modified problem is a shortest path of the initial problem containing a maximal number of elements of B.

[deanhystad]

I find this confusing.

I think a shortest path in this modified problem is a shortest path of the initial problem containing a maximal number of elements of B.

I also find the initial description confusing.

So compiled a list of paths from 0 to 5
0 1 3 4 5
0 1 3 5
0 2 3 4 5
0 2 3 5

Paths with the maximum number of nodes in B {1, 2, 4} are 0, 1, 3, 4, 5 and 0, 2, 3, 4, 5 which both include 2 nodes from B.

Shortest paths are 0, 1, 3, 5 and 0, 2, 3, 5, but they each only include 1 node from B.

So what is more important, minimum length or maximum inclusion?

[Gribouillis]

I find this confusing.

I think a shortest path in this modified problem is a shortest path of the initial problem containing a maximal number of elements of B.

I mean that a path from s to t with minimal sum of weights in the modified problem is also

1. A shortest path from s to t in the initial graph
   
2. Among these shortest paths, a path that contains a maximal number of elements of B.
   

[Pedroski55]

I'm confused about what you wish to achieve. Maybe you could be clearer.

I don't know why you want all those variables, you have enough with E: E.keys() = V, G is redundant, as are s and t

E = {0: [1, 2], 1: [3], 2: [3], 3: [4, 5], 4: [5], 5: []}

Starting with count = [0, -1, -1, -1, -1, -1] and queue = [0]

queue = [0]    
for key in E.keys(): # E.keys() = V
    # current = key
    print(f'key is {key}')
    for neighbour in E[key]: # starts as [1, 2]
        print(f'neighbour is {neighbour}')
        # count was defined as [0, -1, -1, -1, -1, -1] so first key = 0 will be skipped       
        if count[neighbour] == -1: # all count[key] begin life as -1, count[s] later defined as 0
            print(f'count[neighbour] is {count[neighbour]}')
            count[neighbour] = count[key] # count[current] = 0, count[s] = 0 # s defined as 0 
            print(f'count[neighbour] now is {count[neighbour]}')     
            if neighbour in B: # B = {1, 2, 4} 1, 2 and 4 are in B
                print(f'neighbour = {neighbour} and {neighbour} is in {B}') 
                count[neighbour] += 1
                print(f'count[neighbour] = {count[neighbour]}')
                queue.append(neighbour)
                print(f'queue now is {queue}')

Output:
count
[0, 1, 1, 1, 2, 1]

I am not sure what you want the while loop to do!

[deanhystad]

Generating a list of all paths is easy using recursion.

def walk(nodes, target, path, all_paths):
    """Walk nodes looking for target.  When found, add path to list of all paths""".
    if path[-1] == target:
        all_paths.append(path.copy())
    else:
        for node in nodes.get(path[-1], []):
            if node not in path:
                path.append(node)
                walk(nodes, target, path, all_paths)
                path.pop(-1)

[Gribouillis]

I once posted an implementation of Dijkstra algorithm that solves the problem.