Swift Coding Test Course, Bellman-Ford

Hello! In this course, we will discuss the Bellman-Ford algorithm using Swift. The Bellman-Ford algorithm is designed to find the shortest path from a single source to all vertices in a graph, and it has the advantage of being usable in graphs with negative edge weights. In this lecture, we will explain the concept of the Bellman-Ford algorithm and examine the specific implementation process of the algorithm.

1. Overview of the Bellman-Ford Algorithm

The Bellman-Ford algorithm was developed by Richard Bellman and Lester Ford in 1958. The algorithm operates in the following manner:

• Updates the initialized distance array for all edges in the graph.
• Performs relaxation of edges up to the maximum number of vertices – 1 to optimize the distance information.
• Adds a negative cycle check to verify if a negative cycle exists.

1.1. Algorithm Procedure

1. Set the initial distance to infinity and initialize the starting vertex’s distance to 0.
2. Perform relaxation for all edges up to a maximum of V-1 times.
3. Finally, check for negative cycles on all edges.

2. Defining the Problem

Now let’s define a problem where the Bellman-Ford algorithm can be used.

Problem: Finding the Shortest Path

Given the number of vertices in the graph V, the number of edges E, and the information of the edges, find the shortest path from the starting vertex to all other vertices. If the graph contains a negative cycle, output “Negative Cycle”.

Input Format

V (number of vertices)
E (number of edges)
Edge information (starting vertex, ending vertex, weight)

Output Format

Shortest distance to each vertex or "Negative Cycle"

3. Implementation of the Bellman-Ford Algorithm

Now that we have defined the problem, let’s implement the algorithm using Swift.

import Foundation

struct Edge {
    let from: Int
    let to: Int
    let weight: Int
}

func bellmanFord(vertices: Int, edges: [Edge], start: Int) -> [Int] {
    var distances = Array(repeating: Int.max, count: vertices)
    distances[start] = 0

    // Relaxation phase
    for _ in 0..

let edges = [
    Edge(from: 0, to: 1, weight: 4),
    Edge(from: 0, to: 2, weight: 1),
    Edge(from: 2, to: 1, weight: 2),
    Edge(from: 1, to: 3, weight: 1),
    Edge(from: 2, to: 3, weight: 5)
]

let result = bellmanFord(vertices: 4, edges: edges, start: 0)
if !result.isEmpty {
    for (index, distance) in result.enumerated() {
        print("Vertex \(index): \(distance)")
    }
}