Logically determine shortest path

Question

So far I've created all the names for the positions, and now I'm writing a method that will return an array for the "positions" that will be required to take to reach the end goal. This array will then be used against a method to determine how much "time" it should take to get there. However, I'm now stuck to determine a method for a logical path.

So, each position will have relative positions that it connects to. Example;

NSArray *posAlphaConnections = [[NSArray alloc] initWithObjects:@"posDelta",@"posBravo",@"posFoxtrot", nil];

NSDictionary *posAlpha = @{@"connections":posAlphaConnections,
                           @"time":positionCrossTimeAlpha};

_positions = @{     @"posAlpha":posAlpha,
                    @"posBra....
                    }; //NSDictionary

So you end up with a pathway

The Problem Is

-(NSArray *)returnPathWithPlayer:(PlayerClass *)player andGoal:(NSString *)goal {

    NSString *currentPosition = player.position;

    //Up to here

    return 0;
}

I'm currently in the mind thinking.. That I should run a loop for every possible connection.. Of every possible next connection until the goal is reached, then keep the route that returns the shortest distance..? Then use that route.. However, I can't logically think of how to write that.

PS: I'll also add, that each position holds a size variable for the "length of time" it takes to cross that position. So this should also be taken into consideration as opposed to least amount of positions, least amount of time should be the priority.

EDIT:

-(NSArray *)returnPathWithPlayer:(PlayerClass *)player andGoal:(NSString *)goal {

    NSString *currentPosition = player.position;

    NSLog(@"current Position %@", currentPosition);

    NSArray *connections = [[_positions valueForKey:currentPosition] valueForKey:@"connections"];

    __block BOOL pathFound = false;

    for (int i = 0; i < [connections count]; i++) {
        if ([connections[i] isEqualToString:goal]) {
            pathFound = true;
        } else {
            for (int j = 0; j < [[[_positions valueForKey:connections[i]] valueForKey:@"connections"] count]; j++) {
                if ([[[_positions valueForKey:connections[i]] valueForKey:@"connections"][j] isEqualToString:goal]) {
                    pathFound = true;
                }
            }
        }
    }

    if (pathFound) {
        NSLog(@"path to %@ found", goal);
    } else {
        NSLog(@"path to %@ not-found", goal);
    }

    return 0;
}

Here is where my logic is taking me, however, each else will represent a new possibility.. Which, could be more than I'm expecting.. So how can I write this better?

Answer 1

You are looking for the shortest path between two nodes in a graph. Dijkstra's Algorithm is a good and simple Breadth-First Search for this problem.