本文共 1989 字，大约阅读时间需要 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算法，计算图中节点间的最短路径。

转载地址：http://ceifk.baihongyu.com/