Dijkstra in Objective-C

gistfile1.m

//
//  main.m
//  Dijkstra
//
//  Created by Richard S on 12/01/2015.
//  Copyright (c) 2015 Richard Sbresny. All rights reserved.
//

#import <UIKit/UIKit.h>
#import "AppDelegate.h"

@interface Graph : NSObject

@property (nonatomic, strong) NSArray *graph;

@end

@implementation Graph

@end

@interface Vertex : NSObject

@property (nonatomic, strong) NSString *key;
@property (nonatomic, strong) NSArray *neighbours;

@end

@implementation Vertex

@end

@interface Edge : NSObject

@property (nonatomic, strong) Vertex *destinationVertex;
@property (nonatomic, assign) NSInteger distance;

@end

@implementation Edge

- (id)initWithDestination:(Vertex *)destination andDistance:(NSInteger)distance {
	
	if (self = [super init]) {
		self.destinationVertex = destination;
		self.distance = distance;
	}
	return self;
}

@end

@interface Dijkstra : NSObject
@end
@implementation Dijkstra

+ (NSArray *)getShortestPath:(Graph *)inputGraph {
	
	NSMutableDictionary *distances = [NSMutableDictionary dictionary];
	NSMutableDictionary *foundPaths = [NSMutableDictionary dictionary];
	NSMutableArray *queue = [inputGraph.graph mutableCopy];
	
	for (Vertex *vertex in queue) {
		distances[vertex.key] = @(INT_MAX);
		foundPaths[vertex.key] = [NSNull null];
	}
	
	Vertex *currentNode = queue[0];
	distances[currentNode.key] = @(0);
	
	while ([queue count]) {
		
		// find the closest node
		Vertex *closestNode = nil;
		NSInteger closestDistance = INT_MAX;
		for (Vertex *vertex in queue) {
			if (closestNode == nil || [distances[vertex.key] integerValue] < closestDistance) {
				closestNode = vertex;
				closestDistance = [distances[vertex.key] integerValue];
			}
		}
		
		[queue removeObject:closestNode];
		
		if (closestNode.neighbours != nil) {
			for (Edge *neighbour in closestNode.neighbours) {
				
				NSInteger distance = [distances[closestNode.key] integerValue] + neighbour.distance;
				if (distance < [distances[neighbour.destinationVertex.key] integerValue]) {
					distances[neighbour.destinationVertex.key] = @(distance);
					foundPaths[neighbour.destinationVertex.key] = @(distance);
				}
			}
		}
		
	}
	
	Vertex *startNode = inputGraph.graph.firstObject;
	Vertex *targetNode = inputGraph.graph.lastObject;
	NSMutableArray *shortest = [@[startNode.key] mutableCopy];
	while (startNode != targetNode) {

		Vertex *closest = nil;
		NSInteger closestDistance = INT_MAX;
		for (Edge *edge in startNode.neighbours) {
			if (closest == nil || [distances[edge.destinationVertex.key] integerValue] < closestDistance) {
				closestDistance = [distances[edge.destinationVertex.key] integerValue];
				closest = edge.destinationVertex;
			}
		}
		
		[shortest addObject:closest.key];
		startNode = closest;
	}
	
	return [NSArray arrayWithArray:shortest];
}

@end


int main(int argc, char * argv[]) {
	@autoreleasepool {
		Vertex *a = [[Vertex alloc] init];
		a.key = @"a";
		Vertex *b = [[Vertex alloc] init];
		b.key = @"b";
		Vertex *c = [[Vertex alloc] init];
		c.key = @"c";
		Vertex *d = [[Vertex alloc] init];
		d.key = @"d";

		Edge *ab = [[Edge alloc] initWithDestination:b andDistance:11];
		Edge *ac = [[Edge alloc] initWithDestination:c andDistance:5];
		a.neighbours = @[ab, ac];
		
		Edge *bd = [[Edge alloc] initWithDestination:d andDistance:2];
		b.neighbours = @[bd];
		
		Edge *cd = [[Edge alloc] initWithDestination:d andDistance:4];
		c.neighbours = @[cd];
		
		Graph *graph = [[Graph alloc] init];
		graph.graph = @[a, b, c, d];
		
		NSArray *shortestPath = [Dijkstra getShortestPath:graph];
		NSLog(@"%@", [shortestPath componentsJoinedByString:@" ~> "]);
		
	}
}