find the shortest distance in a graph in swift

One of the most efficient algorithms to find the shortest distance in a graph is Dijkstra's algorithm. It works by maintaining a priority queue and visiting the closest unvisited node first, updating the distances from the source node as it goes. Here's how you can implement it in Swift:


main.swift
typealias Edge = (node: Int, weight: Int)
typealias Graph = [Int: [Edge]]

func dijkstra(_ graph: Graph, start: Int) -> [Int] {
    var distances = [Int: Int]() // distance from start to node
    var pq = [(node: start, distance: 0)] // priority queue of nodes to visit
    
    while let (node, distance) = pq.popLast() {
        guard distances[node] == nil else { continue } // already visited
        
        distances[node] = distance
        
        for edge in graph[node] ?? [] {
            guard distances[edge.node] == nil else { continue } // already visited
            
            let next = (node: edge.node, distance: distance + edge.weight)
            let index = pq.firstIndex(where: { $0.distance > next.distance }) ?? pq.endIndex
            pq.insert(next, at: index)
        }
    }
    
    return distances.map { $0.value }
}
854 chars
24 lines

You can call this function with your graph, specifying the starting node:


main.swift
let graph: Graph = [
    1: [(2, 7), (3, 9), (6, 14)],
    2: [(1, 7), (3, 10), (4, 15)],
    3: [(1, 9), (2, 10), (4, 11), (6, 2)],
    4: [(2, 15), (3, 11), (5, 6)],
    5: [(4, 6), (6, 9)],
    6: [(1, 14), (3, 2), (5, 9)]
]
let distances = dijkstra(graph, start: 1)
270 chars
10 lines

This will return an array of distances from the starting node to each node in the graph. For example, distances[4] will give you the shortest distance from node 1 to node 4.

similar swift code snippets

hello world in swift

loop in swift

protocol in swift

sort a list of people by name in swift

make a table view in swift

how do you determine if a string is a palindrome in swift

make http get request in swift

create an enum in swift

create a generic function in swift

open a new view in swift

related categories