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

Objective-C实现最短路径Dijkstra算法

下面是使用Objective-C实现Dijkstra算法的完整源码示例。该示例展示了一个简单的图结构，并使用Dijkstra算法计算从起始节点到所有其他节点的最短路径。

代码概述

算法原理

Dijkstra算法是一种最短路径算法，适用于图中每条边的权重不为负数的情况。其核心思想是：

• 从起始节点开始，初始化所有节点的距离为无穷大，起始节点的距离设为0。
• 使用优先队列（优先级队列）来存储待处理的节点，优先处理距离最近的节点。
• 对每个节点，检查其所有邻接节点，更新其距离并将其重新加入队列。

代码实现

#import 
   
    
@interface Graph : NSObject
@property (nonatomic, strong) NSMutableDictionary *nodes;
@end
@implementation Graph
- (id)initWithNodes:(NSDictionary *)nodes {
    self.nodes = nodes;
    return self;
}
- (NSArray *)dijkstraFromStart:(id)startNode {
    // 初始化所有节点的距离为无穷大
    NSMutableDictionary *distance = [NSMutableDictionary new];
    for (id node in self.nodes) {
        [distance setObject:[NSNumber numberWithDouble:INF) forKey:node];
    }
    [distance setObject:[NSNumber numberWithDouble:0] forKey:startNode];
    
    // 使用优先队列来存储待处理的节点
    PriorityQueue *priorityQueue = [PriorityQueue new];
    [priorityQueue add:startNode withPriority:0];
    
    while (![priorityQueue isEmpty]) {
        id current = [priorityQueue extract];
        if ([distance objectForKey:current] < [priorityQueue getPriorityForElement:current]) {
            continue; // 这个节点已经被处理过更短的路径
        }
        
        // 遍历所有邻接节点
        for (id neighbor in self.nodes[current]) {
            double newDistance = [distance objectForKey:current] + [self.nodes[current][neighbor]];
            if (newDistance < [distance objectForKey:neighbor]) {
                [distance setObject:newDistance forKey:neighbor];
                [priorityQueue add:neighbor withPriority:newDistance];
            }
        }
    }
    
    return [distance keysSortedByValueUsingComparator:^NSComparator _Nonnull(id $0, id $1) {
        return [$0.doubleValue - $1.doubleValue];
    }];
}
   

应用示例

以下是使用该算法的步骤示例：

通过以上实现，您可以轻松地在Objective-C中应用Dijkstra算法，计算图中节点间的最短路径。