Dijkstra Algorithm

ViewController.mm

//
//  ViewController.mm
//  DijkstraAlgorithm
//
//  Created by MizushimaYusuke on 8/11/15.
//  Copyright (c) 2015 MizushimaYusuke. All rights reserved.
//

#import "ViewController.h"

#include <memory>
#include <algorithm>
using namespace std;
#define MAX_NODE 10
#define INF 9999999

class DijkstraSolver {
public:
    void solve(int[][MAX_NODE], int);
private:
    void notify(int, int);
};
void DijkstraSolver::solve(int cost[][MAX_NODE], int nodeCount) {
    bool used[nodeCount];
    int d[nodeCount];
    fill(used, used + nodeCount, false);
    fill(d, d + nodeCount, INF);
    d[0] = 0;
    
    while (true) {
        int n = -1;
        for (int m = 0; m < nodeCount; m++) {
            if (!used[m] && (n == -1 || d[m] < d[n])) n = m;
        }
        if (n == -1) break;
        
        used[n] = true;
        
        for (int m=0; m<nodeCount; m++) {
            d[m] = min(d[m], d[n] + cost[n][m]);
            notify(n, m);
        }
    }
    
    for (int i=1; i<nodeCount; i++) {
        NSLog(@"0-%d  cost:%d", i, d[i]);
    }
};
void DijkstraSolver::notify(int i, int j) {
    if (i != j)
        [[NSNotificationCenter defaultCenter] postNotificationName:@"my message" object:@[@(i), @(j)]];
};

@interface ViewController () {
    int cost[MAX_NODE][MAX_NODE];
}
@property (nonatomic) int count;
@property (nonatomic, strong) NSMutableArray *tasks;
@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    self.view.backgroundColor = [self color:0];
    
    cost[0][1] = 3;
    cost[0][2] = 4;
    cost[1][3] = 1;
    cost[1][4] = 3;
    cost[2][4] = 1;
    cost[3][4] = 3;
    
    CGPoint points[] = {
        CGPointMake(100, 100),
        CGPointMake(220, 100),
        CGPointMake(240, 300),
        CGPointMake(420, 140),
        CGPointMake(500, 280)
    };
    for (int i=0; i<5; i++) {
        UIView *node = [[UIView alloc] initWithFrame:CGRectMake(0, 0, 40, 40)];
        node.tag = i + 1;
        node.center = points[i];
        node.backgroundColor = [self color:1];
        [self.view addSubview:node];
    }
    
    for (int i=0; i<MAX_NODE; i++) {
        for (int j=0; j<MAX_NODE; j++) {
            if (cost[i][j] > 0) {
                UIView *iNode = [self.view viewWithTag:i + 1];
                UIView *jNode = [self.view viewWithTag:j + 1];
                
                UIBezierPath *path = [UIBezierPath bezierPath];
                [path moveToPoint:iNode.center];
                [path addLineToPoint:jNode.center];
                CAShapeLayer *line = [CAShapeLayer layer];
                line.path = path.CGPath;
                line.fillColor = [UIColor clearColor].CGColor;
                line.strokeColor = [self color:1].CGColor;
                line.lineWidth = 2;
                [self.view.layer addSublayer:line];
                
                UILabel *l = [[UILabel alloc] init];
                l.text = [NSString stringWithFormat:@"%d", cost[i][j]];
                l.font = [UIFont boldSystemFontOfSize:30];
                l.textColor = [self color:2];
                [l sizeToFit];
                l.center = CGPointMake((jNode.center.x + iNode.center.x) * 0.5, (jNode.center.y + iNode.center.y) * 0.5);
                [self.view addSubview:l];
            } else {
                cost[i][j] = INF;
            }
        }
    }
    
    [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(receiveMyMessage:) name:@"my message" object:nil];
}

- (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event {
    
    shared_ptr<DijkstraSolver> cppClass(new DijkstraSolver());
    cppClass->solve(cost, 5);
}

- (void)receiveMyMessage:(NSNotification *)note {
    
    self.count++;
    
    UIView *from = [self.view viewWithTag:[note.object[0] intValue] + 1];
    UIView *to = [self.view viewWithTag:[note.object[1] intValue] + 1];
    
    void (^task)(void) = ^{
        [self.view.subviews enumerateObjectsUsingBlock:^(UIView *v, NSUInteger idx, BOOL *stop) {
            if (v.tag > 0) v.backgroundColor = [self color:1];
        }];
        from.backgroundColor = [self color:2];
        to.backgroundColor = [self color:3];
    };
    
    if (!self.tasks) {
        self.tasks = [NSMutableArray array];
        [NSTimer scheduledTimerWithTimeInterval:0.3 target:self selector:@selector(showSearchNode:) userInfo:nil repeats:YES];
    }
    [self.tasks addObject:task];
}

- (void)showSearchNode:(NSTimer *)sender {
    if (self.tasks.count < 1) {
        [sender invalidate];
        return;
    }
    void (^task)(void) = self.tasks.firstObject;
    [self.tasks removeObjectAtIndex:0];
    
    dispatch_async(dispatch_get_main_queue(), ^{
        task();
    });
}

#define ColorHex(rgb) [UIColor colorWithRed:((rgb & 0xFF0000) >> 16)/255.0 green:((rgb & 0xFF00) >> 8)/255.0 blue:(rgb & 0xFF) / 255.0 alpha:1.0]
- (UIColor *)color:(int)i {
    if (i > 3) return nil;
    int colorCode[]  = {0x263248, 0x7E8AA2, 0xFFFFFF, 0xFF9800};
    return ColorHex(colorCode[i]);
}

@end

demo movie : http://lepetit-prince.net/ios/?p=4235