python coding test course, finding the shortest path

Hello! In this article, I would like to talk about the preparation process for algorithm exams for employment. In particular, we will delve deeply into the problem of finding the shortest path. This problem can be encountered in various situations, and the shortest path algorithm, a fundamental concept in graph theory, is frequently asked in job interviews.

Definition of the Shortest Path Problem

The shortest path problem is the problem of finding the shortest path between two nodes in a given graph. Here, the graph is a mathematical representation of networks such as roads and communication networks, composed of vertices and edges. We can use various algorithms to solve this problem, and we will focus on Dijkstra’s algorithm here.

Understanding Dijkstra’s Algorithm

Dijkstra’s algorithm is an efficient algorithm for finding the shortest path from a single vertex to all other vertices in a weighted graph. The algorithm works as follows:

1. Choose a starting vertex and set the distance for that vertex to 0.
2. Update the distances of the vertices connected to the starting vertex.
3. Select the vertex with the shortest updated distance and mark it as ‘visited’.
4. Repeat the process of selecting vertices connected to the visited vertex and updating the distances.
5. Repeat this process until all vertices are visited.

Problem Statement

In this lecture, we will address the problem of finding the shortest path between two vertices when given a graph. The problem can be summarized in the following form:

5 7
0 1 2
0 2 3
1 2 1
1 3 5
2 4 2
3 4 1
4 3 3
0 4

Problem-Solving Process

1. Setting Up the Graph Structure

First, to solve the above problem, we need to set up the graph in an appropriate data structure. Generally, using an adjacency list is efficient in terms of memory and processing speed. In Python, this can be implemented using a dictionary.

2. Implementing Dijkstra’s Algorithm

Next, the libraries needed to implement Dijkstra’s algorithm are as follows:

import heapq
import sys
from collections import defaultdict

Here, heapq is used for the priority queue, and defaultdict is used to easily implement the adjacency list.

3. Example Python Code

Now, let’s write the complete code to find the shortest path:

def dijkstra(graph, start, end):
    # Initialize distances
    distance = {node: float('inf') for node in graph}
    distance[start] = 0
    priority_queue = [(0, start)]  # (distance, vertex)

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # Ignore if a greater value than the current node's distance comes in
        if current_distance > distance[current_node]:
            continue

        # Visit neighboring nodes
        for neighbor, weight in graph[current_node]:
            distance_via_neighbor = current_distance + weight
            if distance_via_neighbor < distance[neighbor]:
                distance[neighbor] = distance_via_neighbor
                heapq.heappush(priority_queue, (distance_via_neighbor, neighbor))

    return distance[end]

# Define the graph
graph = defaultdict(list)
edges = [
    (0, 1, 2),
    (0, 2, 3),
    (1, 2, 1),
    (1, 3, 5),
    (2, 4, 2),
    (3, 4, 1),
    (4, 3, 3)
]

for u, v, w in edges:
    graph[u].append((v, w))

# Calculate the shortest path
start, end = 0, 4
result = dijkstra(graph, start, end)
print(result)  # Output result: 5

4. Code Explanation

The code above uses Dijkstra's algorithm to find the shortest path in the given graph. Each comment allows you to understand the code step by step, but to summarize briefly:

1. Set the graph in dictionary form.
2. Initialize the distance of the starting vertex and add it to the priority queue.
3. Pop a vertex from the queue, investigate its neighbors, update distances, and add them to the queue.
4. After calculating the distances for all vertices, return the distance to the final destination vertex.

Conclusion

The shortest path finding algorithm is one of the important topics in computer science, which may seem simple but can actually be modified in various ways. In addition to Dijkstra's algorithm, there are several methods available, including Bellman-Ford and A* algorithms. In this article, we explored the most basic and widely used Dijkstra's algorithm.

In the future, we will continue to tackle various algorithm problems and delve into more advanced topics. Thank you!