Hello everyone! Today, we will tackle an algorithm problem that finds the shortest path in Swift. This problem is one of the common topics in various algorithm interviews and is based on graph theory. Through this problem, we will gain a deep understanding of the shortest path algorithm known as Dijkstra’s algorithm and implement it in Swift.

Problem Description

There are several cities and roads on the given map. Each city is distinguished by a number, and the roads connect two cities. Each road has a weight, which represents the travel time between the two cities. Your goal is to find the shortest path from one city to another.

Assume that a graph in the following form is given:

  • Number of cities: N (1 ≤ N ≤ 1000)
  • Number of roads: M (1 ≤ M ≤ 10000)
  • Each road connects two cities, and the weight between them is provided.

You will be given the numbers of the starting city and the destination city, and you need to output the weight value of the shortest path.

Input Example

    6 9
    1 2 2
    1 3 5
    2 3 1
    2 4 5
    3 5 2
    4 6 3
    2 5 3
    1 4 9
    5 6 1
    1 6

Output Example

7

(Path: 1 → 2 → 5 → 6)

Problem-Solving Strategy

This problem involves finding the shortest path in a graph and can be solved using Dijkstra’s algorithm. The Dijkstra’s algorithm follows these steps:

  1. Use a priority queue to maintain the minimum distance based on the weights of the stored paths.
  2. Update the path weights to all adjacent nodes from the starting node.
  3. Select the city with the minimum weight and repeat the process of updating the path weights of the neighboring nodes.
  4. When the target city is reached, output that weight.

Swift Code Implementation

    import Foundation

    struct Edge {
        let target: Int
        let weight: Int
    }

    func dijkstra(start: Int, end: Int, graph: [[Edge]], n: Int) -> Int {
        var distances = Array(repeating: Int.max, count: n + 1)
        var priorityQueue: [(Int, Int)] = [] // (distance, city)
        distances[start] = 0
        priorityQueue.append((0, start))

        while !priorityQueue.isEmpty {
            priorityQueue.sort(by: { $0.0 < $1.0 }) // Sort the priority queue
            let (currentDistance, currentCity) = priorityQueue.removeFirst()

            if currentCity == end {
                return currentDistance
            }

            if currentDistance > distances[currentCity] {
                continue
            }

            for edge in graph[currentCity] {
                let newDistance = currentDistance + edge.weight

                if newDistance < distances[edge.target] {
                    distances[edge.target] = newDistance
                    priorityQueue.append((newDistance, edge.target))
                }
            }
        }
        return -1
    }

    func main() {
        let input = """
        6 9
        1 2 2
        1 3 5
        2 3 1
        2 4 5
        3 5 2
        4 6 3
        2 5 3
        1 4 9
        5 6 1
        1 6
        """
        
        var lines = input.components(separatedBy: "\n").filter { !$0.isEmpty }
        let firstLine = lines.removeFirst().split(separator: " ")
        let n = Int(firstLine[0])!
        let m = Int(firstLine[1])!

        var graph = Array(repeating: [Edge](), count: n + 1)

        for line in lines.prefix(m) {
            let parts = line.split(separator: " ")
            let u = Int(parts[0])!
            let v = Int(parts[1])!
            let w = Int(parts[2])!
            graph[u].append(Edge(target: v, weight: w))
            graph[v].append(Edge(target: u, weight: w)) // Undirected graph
        }

        let lastLine = lines.last!.split(separator: " ")
        let start = Int(lastLine[0])!
        let end = Int(lastLine[1])!

        let result = dijkstra(start: start, end: end, graph: graph, n: n)
        print(result)
    }

    main()

Description and Code Analysis

This code first reads the graph and defines the `Edge` struct to represent the edges between cities. The `dijkstra` function is defined to implement Dijkstra's algorithm, initializing the necessary variables and the priority queue. It then calculates the path weights from the current city to all adjacent cities and iteratively finds the shortest path.

Using Swift's arrays and basic data structures allows for an efficient implementation of finding the shortest path. Initializing distances for each city and updating the minimum path through the priority queue is key.

Conclusion

In today's lecture, we learned how to solve the shortest path problem using Swift. Many problems in graph theory often use a similar approach, so if you've mastered Dijkstra's algorithm through this problem, you can apply it to other problems as well.

This is a common topic in interviews and coding tests, so be sure to familiarize yourself with it. In the next session, we will cover another algorithm topic!