ios - 逻辑上确定最短路径

Question

到目前为止，我已经为位置创建了所有名称，现在我正在编写一个方法，该方法将返回一个数组，其中包含为达到最终目标所需的“位置”。然后，该数组将用于确定到达那里需要多少“时间”的方法。但是，我现在无法确定逻辑路径的方法。

因此，每个位置都会有它所连接的相对位置。示例；

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

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

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

所以你最终有一条路

问题是

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

    NSString *currentPosition = player.position;

    //Up to here

    return 0;
}

我目前在想..我应该为每个可能的连接运行一个循环..在达到目标之前的每个可能的下一个连接中，然后保持返回最短距离的路线..？然后使用那条路线。但是，我无法从逻辑上想到如何写。

PS:我还要补充一点，每个仓位都有一个大小变量，表示跨越该仓位所需的“时间长度”。所以这也应该被考虑到，而不是最少的职位，最少的时间应该是优先考虑的。

编辑:

-(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;
}

这就是我的逻辑所带我去的地方，但是，每个其他人都代表了一种新的可能性。这可能比我预期的要多。那么我怎样才能把它写得更好呢？

Answer 1

您正在寻找图中两个节点之间的最短路径。 Dijkstra's Algorithm是针对此问题的一个很好且简单的广度优先搜索。