The BFS (Breadth First Search Algorithm) expands the children nodes level by level, which allows you find the shortest distance between source and every other vertices. However, the graph needs to be unweighted.
unweighted-graph
The Graph can be defined as an neigbour list for above Graph:
1 2 3 4 5 6 7 8 | G = { "A": ["B", "C"], "B": ["A", "C", "D"], "C": ["A", "B", "D", "E"], "D": ["B", "C", "E", "F"], "E": ["C", "D"], "F": ["D"] } |
G = {
"A": ["B", "C"],
"B": ["A", "C", "D"],
"C": ["A", "B", "D", "E"],
"D": ["B", "C", "E", "F"],
"E": ["C", "D"],
"F": ["D"]
}In the following Python code, we use a list as a queue, and perform a BFS and return the result in a dictionary. We also use a set to avoid re-visiting the same vertex.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def BFS(G, s): q = [] q.append(s) seen = set() seen.add(s) parent = {s: None} while (len(q) > 0): vertex = q.pop(0) nodes = G[vertex] for w in nodes: if w not in seen: q.append(w) seen.add(w) parent[w] = vertex return parent |
def BFS(G, s):
q = []
q.append(s)
seen = set()
seen.add(s)
parent = {s: None}
while (len(q) > 0):
vertex = q.pop(0)
nodes = G[vertex]
for w in nodes:
if w not in seen:
q.append(w)
seen.add(w)
parent[w] = vertex
return parentDijkstra Shortest Distance Algorithm from Source to Every Vertex
If the graph is weighted, meaning that the edge will be given a weight.
weighted-graph
The Above weighted Graph can be defined as an adjacent list:
1 2 3 4 5 6 7 8 | G = { "A": {"B": 5, "C": 1}, "B": {"A": 5, "C": 2, "D": 1}, "C": {"A": 1, "B": 2, "D": 4, "E": 8}, "D": {"B": 1, "C": 4, "E": 3, "F": 6}, "E": {"C": 8, "D": 3}, "F": {"D": 6} } |
G = {
"A": {"B": 5, "C": 1},
"B": {"A": 5, "C": 2, "D": 1},
"C": {"A": 1, "B": 2, "D": 4, "E": 8},
"D": {"B": 1, "C": 4, "E": 3, "F": 6},
"E": {"C": 8, "D": 3},
"F": {"D": 6}
}With some modification, and with the help of a priority queue, we can turn the BFS into Dijkstra algorithm that computes the shortest distance between source and every other vertices. A priority queue pops out a element that carries the smallest (highest priority) distance.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | import heapq import math ## initialize the distance from source to every vertex def initDistance(G, s): distance = {s: 0} for vertex in G: if vertex != s: distance[vertex] = math.inf def dijkstra(G, s): pq = [] heapq.heappush(pq, (0, s)) seen = set() seen.add(s) parent = {s: None} distance = initDistance(G, s) while (len(pq) > 0): pair = heapq.heappop(pq) dist = pair[0] vertex = pair[1] nodes = G[vertex].keys() for w in nodes: if w not in seen: # if the vertex is not visited and we find a shorter edge if dist + G[vertex][w] < distance[w]: heapq.heappush(pq, (dist + G[vertex][w], w)) parent[w] = vertex distance[w] = dist + G[vertex][w] return parent, distance |
import heapq
import math
## initialize the distance from source to every vertex
def initDistance(G, s):
distance = {s: 0}
for vertex in G:
if vertex != s:
distance[vertex] = math.inf
def dijkstra(G, s):
pq = []
heapq.heappush(pq, (0, s))
seen = set()
seen.add(s)
parent = {s: None}
distance = initDistance(G, s)
while (len(pq) > 0):
pair = heapq.heappop(pq)
dist = pair[0]
vertex = pair[1]
nodes = G[vertex].keys()
for w in nodes:
if w not in seen:
# if the vertex is not visited and we find a shorter edge
if dist + G[vertex][w] < distance[w]:
heapq.heappush(pq, (dist + G[vertex][w], w))
parent[w] = vertex
distance[w] = dist + G[vertex][w]
return parent, distanceThe idea behind Dijkstra Algorithm is to pop a pair (current shortest distance, and a vertex) from the priority queue, and push a shorter distance/vertex into the queue. Because of using a hash set to remember the visited nodes, both BFS and Dijkstra algorithms can be used on graphs with loops/circular-edges. However, because the way that Dijkstra algorithms finds a shorter edge and pushes into the priority queue, this algorithm does not work for graphs with negative weights.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Algorithm to Sort the Columns of a Matrix using Transpose
Next Post: Algorithms to Compute the SubString with Indexing into an Infinite String
