In the previous articles, we have presented graphs with BFS and DFS. The BFS is actually good to find the path with the fewest nodes. But if the path with the fewest nodes is actually the most expensive, then we face a problem. Imagine a flight with 1 stop that actually costs $500 vs a direct flight that costs $2000. BFS will pick the direct flight ever time, regardless of the price.
To solve that problem and to take the price (or the distance, or any other weight) we need Dijkstra’s Algorithm.
The shortest path with weights is A>C>G>H>P
Dijkstra is actually similar to BFS, but with a major upgrade: it uses a Priority Queue. Instead of exploring the next node in line, it always explores teh cheapest node available anywhere in the graph. Here is the implementation in Python, with heapq. Notice that we track cost_so_far to ensure we never do more work than necessary:
|
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
import heapq def solve_dijkstra(data): lines = data.strip().split("\n") n_edges = int(lines[0].split()[1]) edge_lines = lines[1:1+n_edges] start, end = lines[-1].split() graph = {} for line in edge_lines: u, v, w = line.split() if u not in graph: graph[u] = [] graph[u].append((v, int(w))) pq = [(0, start)] cost_so_far = {start: 0} came_from = {start: None} while pq: current_cost, current_node = heapq.heappop(pq) if current_node == end: #Success! break if current_cost > cost_so_far.get(current_node, float('inf')): continue for n, weight, in graph.get(current_node, []): new_cost = current_cost + weight if new_cost < cost_so_far.get(n, float('inf')): cost_so_far[n] = new_cost came_from[n] = current_node heapq.heappush(pq, (new_cost, n)) path = [] if end in came_from: current = end while current: path.append(current) current = came_from[current] path.reverse() return path, cost_so_far |
Additionally, we have introduced a “Lazy Visualization Trick”, that uses the graph visualization function, presented in a previous article. The idea is to fix the input, without changing the function. Thus, once we have the path (in our case ['A', 'C', 'G', 'H', 'P'], we write a tiny function that takes our raw text data and “stars” the names of the nodes in our path like that:
Abecomes*A*Cbecomes*C*
When we feed this modified text back into our original plotting function, it treats *A* as a new name and displays it with the stars. It is simple, visual way to debug your algorithm without wirting a new visualization engine from scratch.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
def highlight_path_in_data(original_data, path): mapping = {node: f"*{node}*" for node in path} new_lines = [] for line in original_data.strip().split('\n'): parts = line.split() new_parts = [] for word in parts: if word in mapping: new_parts.append(mapping[word]) else: new_parts.append(word) new_lines.append(" ".join(new_parts)) return "\n".join(new_lines) |
Check out the video and the code in GitHub:
Enjoy it!
🏁😺🌞