Question: How to find the shortest path in a graph in swift?
Answer:
// To find the shortest path in a graph, you can use the Dijkstra's algorithm
// Here is an example of using Dijkstra's algorithm to find the shortest path between two nodes in a weighted graph
func dijkstra(graph: [[Int]], start: Int, end: Int) -> [Int] {
let n = graph.count
var dist = Array(repeating: Int.max, count: n)
var visited = Array(repeating: false, count: n)
var prev = Array(repeating: -1, count: n)
dist[start] = 0
for _ in 0..<n {
let u = minDistance(dist: dist, visited: visited)
visited[u] = true
for v in 0..<n {
if !visited[v] && graph[u][v] != 0 && dist[u] != Int.max && dist[u] + graph[u][v] < dist[v] {
dist[v] = dist[u] + graph[u][v]
prev[v] = u
}
}
}
var path = [Int]()
var curr = end
while curr != -1 {
path.insert(curr, at: 0)
curr = prev[curr]
}
return path
}
func minDistance(dist: [Int], visited: [Bool]) -> Int {
var minDist = Int.max
var minIndex = -1
for i in 0..<dist.count {
if !visited[i] && dist[i] <= minDist {
minDist = dist[i]
minIndex = i
}
}
return minIndex
}
/*
You can use the above code by first creating a graph represented by an adjacency matrix and then calling the dijkstra function.
Here is an example of how to use the code to find the shortest path between vertex 0 and vertex 3 in the following graph:
0 -> 1 (weight = 10)
0 -> 2 (weight = 3)
1 -> 3 (weight = 2)
2 -> 1 (weight = 1)
*/
let graph = [[0, 10, 3, 0],
[0, 0, 0, 2],
[0, 1, 0, 0],
[0, 0, 0, 0]]
let start = 0
let end = 3
let path = dijkstra(graph: graph, start: start, end: end)
print("Shortest path: \(path)")
//This will print: Shortest path: [0, 2, 1, 3]
/*
There are several algorithms for finding the shortest path in a graph, such as Dijkstra's algorithm and Bellman-Ford algorithm. The choice of algorithm depends on the specific requirements of the problem, such as whether the graph is weighted or unweighted, directed or undirected, and whether it contains negative weight edges.
*/
Sign up here with your email
ConversionConversion EmoticonEmoticon