Skip to content

Instantly share code, notes, and snippets.

@leeelton leeelton/djikstra.m
Last active Feb 11, 2019

Embed
What would you like to do?
Djikstra's Algorithm in ObjC
// O(E * logV) where E is the number of Edges and V is the number of Vertices
// Why? We process every vertex with extractMin in the pqueue which results in a lgV runtime and we do this for every vertex and their neighbors (edges).
// This results in a (E + V)(lgV) runtime. In a connected graph, V = O(E) therefore our runtime complexity is just O(ElgV).
@interface Pair
@property int vertex;
@property int weight;
+(instanceType)initWithVertex:(int)vertex;
@end
@interface Graph
@property (NSArray<NSArray<Pair *> *> *)vertices;
-(void)addEdge:(Pair *)edge toVertex:(Pair *)vertex;
-(void)addEdge:(Pair *)edge toVertexByIndex:(int)vertexIndex;
@end
- (void)dijkstra(Graph *)graph
{
NSMutableArray<NSNumber *> *distances = [[NSMutableArray alloc] init];
for (int i = 0; i < graph.vertices.count; ++i) {
distance[i] = @(INT_MAX);
}
distance[0] = 0;
// pqueue which receives Pair objects and sorts them by weight (min-heap with min weight)
PriorityQueue* pqueue = [[PriorityQueue alloc] init];
NSArray *source = [[Pair alloc]initWithVertex:0 weight:0];
[pqueue addObject:source];
while (!pqueue.empty) {
Pair *currentMinVertex = [pqueue extractMin];
NSArray<Pair *> *neighbors = [self getNeighborsOfVertex: currentMinVertex];
for (int i = 0; i < neighbors.count; ++i) {
let tempDistance = distance[currentMinVertex.vertex] + neighbors[i].weight;
distance[neighbors[i].vertex] = MIN(tempDistance, distance[neighbors[i].vertex]);
[pqueue insert: neighbors[i]];
}
}
for (int i = 0; i < distance.count; ++i) {
NSLog(@"Distance from node #%d: %d", i, distance[i]);
}
}
- (NSArray<Pair *> *neighbors)getNeighborsOfVertex:(Pair *)vertex inGraph:(Graph *)graph
{
return graph.vertices[vertex.vertex];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.