python coding test course, Dijkstra

Hello, everyone! Today, we will take a deep dive into the Dijkstra’s Algorithm and solve problems that are frequently asked in coding tests. Dijkstra’s Algorithm is an algorithm used to find the shortest path in a weighted graph, primarily used to solve network shortest path problems.

1. Overview of Dijkstra’s Algorithm

Dijkstra’s Algorithm, developed by Edsger Dijkstra in 1956, is a shortest path algorithm used to find the shortest path from a specific vertex to all other vertices. This algorithm does not allow negative weights and assumes that the graph is connected.

1.1 Algorithm Operating Principle

  • Select a starting vertex and set its distance to 0.
  • Initialize the distance of all other vertices to infinity.
  • Select the vertex with the shortest distance among the vertices whose minimum distance has not yet been determined.
  • Update the distances of adjacent vertices based on the selected vertex.
  • Repeat until the distances of all vertices are determined.

2. Problem Description

Now let’s apply Dijkstra’s Algorithm through a real problem.

Problem: Find the Shortest Path

Write a program to find the shortest path from a specific starting vertex to all other vertices given a graph provided as input.

Input Conditions

  • The first line contains the number of vertices V and the number of edges E. (1 ≤ V ≤ 20, 1 ≤ E ≤ 100)
  • From the second line onwards, information about each edge is provided over E lines. Edge information is given in the form of the starting vertex A, ending vertex B, and weight C.
  • The last line contains the starting vertex K.

Output Conditions

Output the shortest distance from the starting vertex K to all other vertices. If there is no path to any vertex, output INF.

3. Problem Solving Process

3.1 Graph Representation

First, we represent the graph as an adjacency list based on the given edge information. In Python, we can use a dictionary to store each vertex and the other vertices connected to it along with their weights.

from collections import defaultdict
import heapq

def create_graph(edges):
    graph = defaultdict(list)
    for A, B, C in edges:
        graph[A].append((B, C))
    return graph

3.2 Implementing Dijkstra’s Algorithm

Now we will implement Dijkstra’s Algorithm. This algorithm efficiently updates the shortest path found so far using a priority queue.

def dijkstra(graph, start, V):
    distances = {vertex: float('inf') for vertex in range(1, V + 1)}
    distances[start] = 0
    priority_queue = [(0, start)]

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

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

3.3 Final Code

We compile all elements to write the final code, which also includes the input handling and result processing parts.

def main():
    V, E = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(E)]
    K = int(input())

    graph = create_graph(edges)
    distances = dijkstra(graph, K, V)

    for vertex in range(1, V + 1):
        if distances[vertex] == float('inf'):
            print("INF")
        else:
            print(distances[vertex])

if __name__ == "__main__":
    main()

4. Time Complexity

The time complexity of Dijkstra’s Algorithm varies depending on the data structures used. Typically, when using a priority queue, the time complexity is O((V + E) log V), where V is the number of vertices and E is the number of edges.

5. Conclusion

In this lecture, we learned how to solve the shortest path problem using Dijkstra’s Algorithm and handled real input. This algorithm can be utilized in various fields such as networking and game development, so it’s good to have a firm grasp of it.

Practice various scenarios through additional problems. In the next lecture, we will look at another algorithm. Thank you!