本文共 3290 字，大约阅读时间需要 10 分钟。

Objective-C实现图的弗洛伊德-沃舍尔算法

概念回顾

弗洛伊德-沃舍尔（Floyd-Warshall）算法是一种经典的最短路径算法，广泛应用于图论中。其核心思想是通过动态规划的方法，逐步更新所有节点之间的最短路径。该算法的时间复杂度为O(n³)，适用于节点数较少的图表。

基本步骤

代码实现

#import 
   
    
#define INF 99999
@interface FloydWarshall : NSObject
@end
@implementation FloydWarshall
- (void)computeShortestPathFromNodeAtoNodeB:(NSInteger)source
         toNode:(NSInteger)destination
         inGraph:(NSDictionary *)graph {
    NSInteger n = [graph.keys count]; // 节点数
    NSInteger distance[n][n]; // 初始化距离矩阵
    // 初始化距离矩阵
    for (NSInteger i = 0; i < n; i++) {
        for (NSInteger j = 0; j < n; j++) {
            distance[i][j] = (i == j) ? 0 : INF;
        }
    }
    // 设置初始边权重
    for (NSInteger i = 0; i < n; i++) {
        NSDictionary edges = [graph objectForKey:i];
        for (NSDictionary *edge in edges) {
            NSInteger to = [edge key];
            NSInteger weight = [edge objectForKey:@"weight"];
            distance[i][to] = weight;
        }
    }
    // Floyd-Warshall算法
    for (NSInteger k = 0; k < n; k++) {
        for (NSInteger i = 0; i < n; i++) {
            for (NSInteger j = 0; j < n; j++) {
                if (distance[i][k] + distance[k][j] < distance[i][j]) {
                    distance[i][j] = distance[i][k] + distance[k][j];
                }
            }
        }
    }
    return distance[source][destination];
}
- (NSDictionary *)graphWithNodes:(NSArray *)nodes
                      edges:(NSDictionary *)edges {
    // 初始化图表
    NSMutableDictionary *graph = [NSMutableDictionary dictionary];
    NSInteger n = [nodes count];
    for (NSInteger i = 0; i < n; i++) {
        [graph setObject: [NSMutableDictionary dictionary] forKey:i];
    }
    // 添加边
    for (NSDictionary *edge in edges) {
        NSInteger from = [edge objectForKey:@"from"];
        NSInteger to = [edge objectForKey:@"to"];
        NSInteger weight = [edge objectForKey:@"weight"];
        if ([graph objectForKey:from]) {
            [[graph objectForKey:from] setObject: [NSDictionary dictionaryWithKeyValues:
                                               @{@"to": to, @"weight": weight}] forKey:to];
        }
    }
    return graph;
}
- (void)exampleUsage {
    // 节点列表
    NSArray *nodes = @[@0, @1, @2, @3];
    // 边列表
    NSDictionary *edges = @{
        @0: @{
            @1: @{ @"weight": @5 },
            @2: @{ @"weight": @2 }
        },
        @1: @{
            @2: @{ @"weight": @3 },
            @3: @{ @"weight": @10 }
        },
        @2: @{
            @3: @{ @"weight": @15 }
        }
    };
    // 创建图表
    NSDictionary *graph = [self graphWithNodes:nodes edges:edges];
    // 计算节点0到节点3的最短路径
    NSInteger shortestPath = [self computeShortestPathFromNodeAtoNodeB:0 toNode:3 inGraph:graph];
    NSLog(@"最短路径长度为：%ld", shortestPath);
}
@end
   

解释

通过上述步骤，可以在Objective-C中实现Floyd-Warshall算法，准确计算出图中任意两节点之间的最短路径。