CODEWITHSUNDEEP
algorithmdata-structuresgraphshortest-path
YoYo
YoYo

Reputation: 23

How can i find the shortest path from any node to a set A

I have an un-directed graph 'G' and a set 'A' of nodes in the graph G

I'm struggling with finding an efficient algorithm that finds the the shortest paths from any node in the graph G to the closest node in the set 'A'

I thought about this: having a minimum distance array to all nodes, Running BFS algorithm on each node in set A and after BFS completion, update the array if a shorter path was found, this time complexity is O(k(n+m)) - which is a lot when as K grows, I was told there is a more efficient algorithm i can use. Please note, I'm only allowed to use BFS algorithm in this exercise

Upvotes: 2

Views: 175

Answers (2)

tobias_k
tobias_k

Reputation: 82899

You really just need a single pass of your BFS algorithm if you start with all the nodes from A in the initial queue.

  • keep track of already visited nodes and their paths to nodes from A in a map/dictionary
  • initialize the BFS queue with tuples (a, empty_path) for each node a in your A set
  • while there are more elements in the queue, pop the next node and path from the queue
  • if the node is already in the visited map, skip it
  • otherwise, add it to visited with the given path
  • add neighbor nodes to the queue with extended paths

Example in Python:

# 2--0--1
# |     |
# 3     4
graph = {0: [1, 2], 1: [0, 4], 2: [0, 3], 3: [2], 4: [1]}
A = [2, 0]

import collections
queue = collections.deque([(a, []) for a in A])
visited = {}
while queue:
    cur, path = queue.popleft()
    if cur in visited: continue
    visited[cur] = path
    for node in graph[cur]:
        queue.append((node, [cur] + path))
print(visited)
# {2: [], 0: [], 3: [2], 1: [0], 4: [1, 0]}

Upvotes: 0

Dave
Dave

Reputation: 9085

Create an extra node that had edges to every node in 'A.' Run BFS from this extra node. The distance from every node to the closest node in 'A' is 1 less than the distance to this extra node.

Upvotes: 2

Related Questions