Порядок работы программы.

1. Проводим инициализацию графа.

 

_graph = [[Graph alloc] init];

 

2. После того, как пользователь кликнет по кнопке «Start», выполняется следующее действие:

 

- (IBAction)startButtonPressed:(id)sender

{

NSLog(@"Start button pressed");

[self dijkstra];

}

 

Из которого вызывается метод dijkstra.

 

3. Метод dijkstra реализует работу алгоритма Дейкстры.

 

- (void)dijkstra {

NSMutableArray *unVisited = [[NSMutableArray alloc] initWithCapacity:[self.graph.nodes count]];

NSMutableArray *distance = [[NSMutableArray alloc] initWithCapacity:[self.graph.nodes count]];

NSMutableArray *previous = [[NSMutableArray alloc] initWithCapacity:[self.graph.nodes count]];

 

// Стартовая вершина ("S")

Node *startNode = self.canvas.start;

// Конечная вершина ("T")

Node *endNode = self.canvas.end;

 

for (Node *node in self.graph.nodes) {

[distance addObject:[NSNumber numberWithFloat:INFINITY]];

[previous addObject:startNode];

}

 

 

[distance replaceObjectAtIndex:[self indexOfNode:startNode] withObject:[NSNumber numberWithInt:0]];

[unVisited addObjectsFromArray:self.graph.nodes];

 

 

while ([unVisited count]!= 0) {

 

Node *nodeWithMinPath = [unVisited objectAtIndex:0];

NSNumber *minNum = [distance objectAtIndex:[self indexOfNode:nodeWithMinPath]];

for (Node *node in unVisited) {

if ([minNum floatValue] > [[distance objectAtIndex:[self indexOfNode:node]] floatValue]) {

minNum = [distance objectAtIndex:[self indexOfNode:node]];

nodeWithMinPath = node;

}

}

 

[unVisited removeObject:nodeWithMinPath];

 

if ([[distance objectAtIndex:[self indexOfNode:nodeWithMinPath]] floatValue] == INFINITY)

break;

 

for (Path *pathToFriend in nodeWithMinPath.pathToFriends) {

if ([unVisited containsObject:pathToFriend.connectedNode] == NO) {

continue;

}

 

 

NSNumber *alt = [NSNumber numberWithFloat:[[distance objectAtIndex:[self indexOfNode:nodeWithMinPath]] floatValue] + [[NSNumber numberWithInteger:pathToFriend.edgeCost] floatValue]];

 

if ([alt floatValue] < [[distance objectAtIndex:[self indexOfNode:pathToFriend.connectedNode]] floatValue]) {

[distance replaceObjectAtIndex:[self indexOfNode:pathToFriend.connectedNode] withObject:alt];

[previous replaceObjectAtIndex:[self indexOfNode:pathToFriend.connectedNode] withObject:nodeWithMinPath];

}

}

}

 

// Show result

NSMutableArray *reverseResult = [[NSMutableArray alloc] init];

 

Node *node = endNode;

[reverseResult addObject:node];

while (node!= startNode) {

node = [previous objectAtIndex:[self indexOfNode:node]];

[reverseResult addObject:node];

}

 

NSString *result = @"Path: ";

for (int i = (int)[reverseResult count]-1; i >= 0; i--) {

Node *foo = [reverseResult objectAtIndex:i];

NSLog(@"res: '%i'", foo.value);

result = [result stringByAppendingFormat:@"%i ", foo.value];

}

 

NSNumber *resultSum = [distance objectAtIndex:[self indexOfNode:endNode]];

NSLog(@"resultSum: %f", [resultSum floatValue]);

result = [result stringByAppendingFormat:@"\nShortest Path Cost: %f ", [resultSum floatValue]];

[self.resultLabel setStringValue:result];

}