nhudinhtuan · April 6, 2020 13:53
diff --git a/find_shortest_path_unweight.py b/find_shortest_path_unweight.py
 from collections import deque
 # graph is represented by adjacency list: List[List[int]]
 # s: start vertex
 # d: destination vertex
 # based on BFS
 def find_shortest_path(graph, s, d):
    # pred[i] stores predecessor of i in the path
    pred = [-1] * len(graph)
    # set is used to mark visited vertices
    visited = set()
    # create a queue for BFS
    queue = deque()
    # Mark the start vertex as visited and enqueue it
    visited.add(s)
    queue.appendleft(s)

    while queue:
        current_vertex = queue.pop()
        # Get all adjacent vertices of current_vertex
        # If a adjacent has not been visited, then mark it
        # visited and enqueue it
        for v in graph[current_vertex]:
            if v not in visited:
                visited.add(v)
                queue.appendleft(v)
                # record the predecessor
                pred[v] = current_vertex
                # reach to the destination
                if v == d:
                    break

    # no path to d
    if pred[d] == -1:
        return []
    # retrieve the path
    path = [d]
    current = d
    while pred[current] != -1:
        current = pred[current]
        path.append(current)

    return path[::-1]
	from collections import deque
	# graph is represented by adjacency list: List[List[int]]
	# s: start vertex
	# d: destination vertex
	# based on BFS
	def find_shortest_path(graph, s, d):
	# pred[i] stores predecessor of i in the path
	pred = [-1] * len(graph)
	# set is used to mark visited vertices
	visited = set()
	# create a queue for BFS
	queue = deque()
	# Mark the start vertex as visited and enqueue it
	visited.add(s)
	queue.appendleft(s)

	while queue:
	current_vertex = queue.pop()
	# Get all adjacent vertices of current_vertex
	# If a adjacent has not been visited, then mark it
	# visited and enqueue it
	for v in graph[current_vertex]:
	if v not in visited:
	visited.add(v)
	queue.appendleft(v)
	# record the predecessor
	pred[v] = current_vertex
	# reach to the destination
	if v == d:
	break

	# no path to d
	if pred[d] == -1:
	return []
	# retrieve the path
	path = [d]
	current = d
	while pred[current] != -1:
	current = pred[current]
	path.append(current)

	return path[::-1]