Skip to content

Instantly share code, notes, and snippets.

@VivienGiraud
Forked from pocketkk/Swift - Dijkstra.swift
Created October 27, 2016 09:39
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save VivienGiraud/f03c128bf4bc907adb8a3fadf1b1b331 to your computer and use it in GitHub Desktop.
Save VivienGiraud/f03c128bf4bc907adb8a3fadf1b1b331 to your computer and use it in GitHub Desktop.
Swift 3 - Shortest Path Algorithm (Compiled from: http://waynewbishop.com/swift/graphs/dijkstra/)
import UIKit
public class Vertex {
var key: String?
var neighbors: Array<Edge>
init() {
self.neighbors = Array<Edge>()
}
}
public class Edge {
var neighbor: Vertex
var weight: Int
init() {
weight = 0
self.neighbor = Vertex()
}
}
class Path {
var total: Int!
var destination: Vertex
var previous: Path!
//object initialization
init(){ destination = Vertex() }
}
public class SwiftGraph {
private var canvas: Array<Vertex>
public var isDirected: Bool
init() {
canvas = Array<Vertex>()
isDirected = true
}
//create a new vertex
func addVertex(key: String) -> Vertex {
//set the key
let childVertex: Vertex = Vertex()
childVertex.key = key
//add the vertex to the graph canvas
canvas.append(childVertex)
return childVertex
}
func addEdge(source: Vertex, neighbor: Vertex, weight: Int) {
//create a new edge
let newEdge = Edge()
//establish the default properties
newEdge.neighbor = neighbor
newEdge.weight = weight
source.neighbors.append(newEdge)
//check for undirected graph
if (isDirected == false) {
//create a new reversed edge
let reverseEdge = Edge()
//establish the reversed properties
reverseEdge.neighbor = source
reverseEdge.weight = weight
neighbor.neighbors.append(reverseEdge)
}
}
func processDijkstra(source: Vertex, destination: Vertex) -> Path? {
var frontier = [Path]()
var finalPaths = [Path]()
//use source edges to create the frontier
for e in source.neighbors {
let newPath: Path = Path()
newPath.destination = e.neighbor
newPath.previous = nil
newPath.total = e.weight
//add the new path to the frontier
frontier.append(newPath)
}
//obtain the best path
var bestPath: Path = Path()
while(frontier.count != 0) {
//support path changes using the greedy approach
bestPath = Path()
var pathIndex: Int = 0
for x in (0..<frontier.count) {
let itemPath: Path = frontier[x]
if (bestPath.total == nil) || (itemPath.total < bestPath.total) {
bestPath = itemPath
pathIndex = x
}
}
for e in bestPath.destination.neighbors {
let newPath: Path = Path()
newPath.destination = e.neighbor
newPath.previous = bestPath
newPath.total = bestPath.total + e.weight
//add the new path to the frontier
frontier.append(newPath)
}
//preserve the bestPath
finalPaths.append(bestPath)
//remove the bestPath from the frontier
frontier.remove(at: pathIndex)
}
printSeperator(content: "FINALPATHS")
printPaths(paths: finalPaths , source: source)
printSeperator(content: "BESTPATH BEFORE")
printPath(path: bestPath, source: source)
for p in finalPaths {
let path = p
if (path.total < bestPath.total) && (path.destination.key == destination.key){
bestPath = path
}
}
printSeperator(content: "BESTPATH AFTER")
printPath(path: bestPath, source: source)
return bestPath
}
func printPath(path: Path, source: Vertex) {
print("BP: weight - \(path.total!) \(path.destination.key!) ")
if path.previous != nil {
printPath(path: path.previous!, source: source)
} else {
print("Source : \(source.key!)")
}
}
func printPaths(paths: [Path], source: Vertex) {
for path in paths {
printPath(path: path, source: source)
}
}
func printLine() {
print("*******************************")
}
func printSeperator(content: String) {
printLine()
print(content)
printLine()
}
}
var graph = SwiftGraph()
var a = graph.addVertex(key: "a")
var a1 = graph.addVertex(key: "a1")
var b = graph.addVertex(key: "b")
var c = graph.addVertex(key: "c")
var d = graph.addVertex(key: "d")
graph.addEdge(source: a, neighbor: d, weight: 1)
graph.addEdge(source: a, neighbor: d, weight: 30)
graph.addEdge(source: a, neighbor: a1, weight: 30)
graph.addEdge(source: a1, neighbor: b, weight: 10)
graph.addEdge(source: a, neighbor: b, weight: 5)
graph.addEdge(source: b, neighbor: c, weight: 21)
graph.addEdge(source: c, neighbor: d, weight: 5)
var path = graph.processDijkstra(source: a, destination: d)
@inigo333
Copy link

@inigo333
Copy link

Actually, I recommend you having a look at his github repo on this matter:
https://github.com/waynewbishop/SwiftStructures

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment