Swift Coding Test Course, Dijkstra

Today, we will solve the problem of finding the shortest path using Dijkstra’s algorithm in Swift. The Dijkstra algorithm is one of the most important algorithms in graph theory and is used to find the shortest path from a specific node to all other nodes.

Introduction to the Algorithm

Dijkstra’s Algorithm is a graph search algorithm developed by computer scientist Edgar Dijkstra in 1956. This algorithm is effective for finding the shortest path in graphs without negative weights.

How It Works

The algorithm proceeds in the following steps:

1. Select the starting node and set the distance of this node to 0.
2. Update the distances to neighboring nodes.
3. After calculating the distances to all nodes, select the closest node and move to the next node.
4. Repeat this process until you find the shortest distance to all nodes.

Example Problem

Here is a problem that can be solved using Dijkstra’s algorithm:

Problem: Find the Shortest Path

Given a graph, find the shortest path from a specific starting node to other nodes. Below is the weighted adjacency list of the graph:

0: {1: 4, 2: 1}
1: {2: 2, 3: 5}
2: {1: 1, 3: 8}
3: {}

For the above graph, write a program to find the shortest path from node 0 to node 3. The result should be able to find the shortest path as 0 -> 2 -> 1 -> 3.

Swift Implementation

Now, let’s implement Dijkstra’s algorithm in Swift to solve the above problem.

import Foundation

// Class to represent the graph
class Graph {
    var vertices: Int
    var adjList: [[(node: Int, weight: Int)]]
    
    init(vertices: Int) {
        self.vertices = vertices
        self.adjList = Array(repeating: [], count: vertices)
    }

    func addEdge(source: Int, destination: Int, weight: Int) {
        adjList[source].append((node: destination, weight: weight))
    }

    func dijkstra(source: Int) -> [Int] {
        var distances = Array(repeating: Int.max, count: vertices)
        var visited = Array(repeating: false, count: vertices)
        distances[source] = 0

        for _ in 0.. Int {
        var min = Int.max
        var minIndex = -1
        
        for v in 0..

In the above code, the graph class uses an adjacency list to store relationships between nodes and calculates the shortest path using Dijkstra's algorithm. It outputs the shortest path from node 0 to node 3 for the given example.

Conclusion

Dijkstra's algorithm is a very useful tool for solving the shortest path problem. By implementing it in Swift, you can understand how the algorithm works and enhance your important coding skills through practical programming exercises. I encourage you to use Dijkstra's algorithm to solve various graph problems.

If you want to learn more about algorithms and solutions, please continue to follow my blog!

관련