dijkstra是用来求最短路径的一种算法，能得出最优解，属于广度优先搜索法
思路分解
图1表示一个有向，有权图
图1
图2表示初始配置，假设开始节点s为v1，第一个选择的顶点为v1，路径的长为0，改顶点标记为已知，既然v1已知，那么某些表项就需要调整，邻接到v1的顶点是是v2，v4，这两个顶点的项得到调整，如图3所示
图2
图3
下一步，选取v4标记为已知。顶点v3，v5，v6，v7时邻接的顶点，对这几个顶点进行调整，如图4
图4
接着选择v2，v4是邻接的点，但已经是已知的，因此不做任何工作。v5是邻接的点，因为经过v2的值为2+10 = 12，而长为3的路径是已知的，图5指出在这些顶点被选取之后的表
图5
下一个选取的顶点是v5，其值为3，。v7是其唯一的邻接顶点，但是它不用调整，因为3+6 > 5.然后选取v3，对v6的距离下调到3+5 = 8，结果如图6
图6
然后选择v7.v6下调到5+1 = 6，如图7
图7
最后我们选择v6，如图8
图8
时间复杂度分析
V表示顶点，E表示边
通过扫描表来得出每一步最小的dv，那么每一步将花费O(V)时间找到最小值，那么整个算法将花费O(V2)来查找最小值dv，每次更新dw的时间为常数，每条边最多有一次更新总计为O(E)，因此总的运行时间为O(V2) + O(E) = O(V2)
如果图是稠密的E和V2成线性关系，这种算法不仅简单，而且几乎是最优的
如果图是稀疏的E = V，那么这种算法就太慢了，需要优化
优化的方式可以采用二叉堆优化
Code
//
// ViewController.m
// ppp
//
// Created by Liashui on 2019/5/18.
// Copyright © 2019年 Liashui. All rights reserved.
//
#import "ViewController.h"
/**
邻接链表节点
*/
@interface Node:NSObject
@property(nonatomic,copy)NSString *name;//名称
@property(nonatomic,assign)NSInteger weight;//权重
@property(nonatomic,strong)Node *next;//下个节点
@end
@implementation Node
@end
/**
辅助数组元素节点
*/
@interface Node1:NSObject
@property(nonatomic,copy)NSString *name;//名称
@property(nonatomic,assign)BOOL known;//是否已经设置
@property(nonatomic,assign)NSInteger d;//当前最短路径
@property(nonatomic,strong)Node1 *p;//移动到当前顶点的上一个顶点
@end
@implementation Node1
@end
@interface ViewController ()
@property(nonatomic,strong)NSMutableArray *array;//邻接链表
@property(nonatomic,strong)NSMutableArray *arrayOne;//辅助数组结构
@end
@implementation ViewController
- (void)viewDidLoad {
[super viewDidLoad];
// Do any additional setup after loading the view, typically from a nib.
//初始化邻接表
[self initArray];
//起点索引
int start = 0;
[self dijkstraWithStart:start];
//终点索引
int end = 5;
Node1 *nodeEnd = self.arrayOne[end];
NSLog(@"v%d",start+1);
[self printRoute:nodeEnd];
}
/**
初始化邻接表
*/
- (void)initArray {
//v1
Node *node2 = [Node new];
node2.name = @"v2";
node2.weight = 2;
node2.next = nil;
Node *node4 = [Node new];
node4.name = @"v4";
node4.weight = 1;
node4.next = node2;
Node *node1 = [Node new];
node1.name = @"v1";
node1.weight = 0;
node1.next = node4;
//v2
Node *nod55 = [Node new];
nod55.name = @"v5";
nod55.weight = 10;
nod55.next = nil;
Node *node44 = [Node new];
node44.name = @"v4";
node44.weight = 3;
node44.next = nod55;
Node *node22 = [Node new];
node22.name = @"v2";
node22.weight = 0;
node22.next = node44;
//v3
Node *nod666 = [Node new];
nod666.name = @"v6";
nod666.weight = 5;
nod666.next = nil;
Node *node111 = [Node new];
node111.name = @"v1";
node111.weight = 4;
node111.next = nod666;
Node *node333 = [Node new];
node333.name = @"v3";
node333.weight = 0;
node333.next = node111;
//v4
Node *node6 = [Node new];
node6.name = @"v3";
node6.weight = 2;
node6.next = nil;
Node *node7 = [Node new];
node7.name = @"v6";
node7.weight = 8;
node7.next = node6;
Node *node8 = [Node new];
node8.name = @"v7";
node8.weight = 4;
node8.next = node7;
Node *node9 = [Node new];
node9.name = @"v5";
node9.weight = 2;
node9.next = node8;
Node *node10 = [Node new];
node10.name = @"v4";
node10.weight = 0;
node10.next = node9;
//v5
Node *node11 = [Node new];
node11.name = @"v7";
node11.weight = 6;
node11.next = nil;
Node *node12 = [Node new];
node12.name = @"v5";
node12.weight = 0;
node12.next = node11;
//v6
Node *node13 = [Node new];
node13.name = @"v6";
node13.weight = 0;
node13.next = nil;
//v7
Node *node14 = [Node new];
node14.name = @"v6";
node14.weight = 1;
node14.next = nil;
Node *node15 = [Node new];
node15.name = @"v7";
node15.weight = 0;
node15.next = node14;
self.array = [[NSMutableArray alloc] initWithObjects:node1,node22,node333,node10,node12,node13,node15, nil];
}
/**
打印路径
@param node 顶点
*/
- (void)printRoute:(Node1 *)node {
if (!node.p) {
return;
}
[self printRoute:node.p];
NSLog(@"%@",node.name);
}
/**
初始化辅助数组
*/
- (void)initArrayOne:(NSInteger)start {
self.arrayOne = [NSMutableArray new];
for (int i = 0; i< self.array.count; i++) {
Node1 *node1 = [Node1 new];
if (i == start) {
node1.d = 0;
node1.known = YES;
} else {
node1.d = 10000;
node1.known = NO;
}
node1.p = nil;
node1.name = [NSString stringWithFormat:@"v%d",i+1];
[self.arrayOne addObject:node1];
}
}
/**
dijkstra算法
@param start 起点index
*/
- (void)dijkstraWithStart:(NSInteger)start{
//初始化
[self initArrayOne:start];
NSInteger knownCount = 1;
NSInteger k = start;
Node1 *tmp = self.arrayOne[k];
tmp.known = YES;
while (1) {
Node *tmp1 = self.array[k];
tmp1 = tmp1.next;
Node1 *tmpN = self.arrayOne[k];
//赋值
while (tmp1) {
NSInteger index = [[tmp1.name stringByReplacingOccurrencesOfString:@"v" withString:@""] integerValue] - 1;
Node1 *tmp2 = self.arrayOne[index];
if (!tmp2.known) {
if (tmpN.d + tmp1.weight < tmp2.d) {
tmp2.d = tmpN.d + tmp1.weight;
tmp2.p = tmpN;
}
}
tmp1 = tmp1.next;
}
//找出最小值
NSInteger min = 1000;
for (int j = 0; j<self.arrayOne.count; j++) {
Node1 *node1 = self.arrayOne[j];
if (!node1.known) {
if (node1.d < min) {
min = node1.d;
k = j;
}
}
}
Node1 *w = self.arrayOne[k];
w.known = YES;
knownCount ++;
if (knownCount == self.arrayOne.count) {
break;
}
}
}
@end
console
2019-05-19 17:20:44.030575+0800 [13576:669580] v1
2019-05-19 17:20:44.030848+0800 [13576:669580] v4
2019-05-19 17:20:44.030994+0800 [13576:669580] v7
2019-05-19 17:20:44.031551+0800 [13576:669580] v6
网友评论