代价一致算法 swift3.0 寻找最小路径 无中间节点
最近在研究仓库沙盘，在多点内寻找最短路径，从迪杰斯特拉到A*都有尝试，最终用了代价一致搜索这个算法。
推荐这个算法的是我的同事，他告诉我能够扩展到中间节点，中间路过点，可我尝试了半天， 最终还是放下中间节点的写法，因为会有bug。
废话不多说了，直接上swift代码。
classGraph{
//从初始点到当前地点的距离之和
vardis =0
//是否被访问
varflag =0
//当前节点的上一个节点
varbef =0
}
classGraphString {
varcities = [String]()//地址名
varpath = [[NSInteger]]()//地址距离
}
classpriceIsConsistentAlgorithm {
//
init(notes:GraphString,beginIndex:Int,endIndex:Int) {
varGraphArray = [Graph]()
foriin0..
letgraph =Graph()
graph.dis=0* i//单纯去掉警告
graph.bef=-1
graph.flag=0
GraphArray.append(graph)
}
ucs_search(notes: notes, begin: beginIndex,end: endIndex, graph: GraphArray)
display(notes: notes, begin: beginIndex, end: endIndex, graph: GraphArray)
}
funcucs_search(notes:GraphString,begin:Int,end:Int,graph:[Graph]){
varlist = [NSInteger]()
//给数组添加起点
list.append(begin)
graph[begin].flag=1
//数组不为空时扩展节点
while!list.isEmpty{
//给数组排序最小到前面
list =sorTLiset(list: list,graph: graph)
letnod = list.removeFirst()//单独拿出最小节点最小节点移除
graph[nod].flag=1
//如果当前节点为目标节点则返回
ifnod == end{return}
foriin0..
//当某个节点和初始点有结合路径，并且不在数组队列里，则加入数组并更新
if(notes.path[nod][i] >=0)&&(graph[i].flag==0) {
if!IsListArray(i:i, list:list){//多点的算法在这里判断！！！！
list.insert(i,at:0)//插入在第一位
graph[i].dis= graph[nod].dis+ notes.path[nod][i]
graph[i].bef= nod
}elseif(graph[nod].dis+notes.path[nod][i] < graph[i].dis){
//如果此节点在队列里面但是从上一个结点到此节点的总路程小于直接到达此节点的路程，则更新dis数组使
//到达此节点的路程为现今的最短，并更新父节点的值
graph[i].dis= graph[nod].dis+ notes.path[nod][i]
graph[i].bef= nod
print("执行了")
}
}
}
}
}
//判断是否在list中
funcIsListArray(i:NSInteger,list:[NSInteger])->Bool{
forjinlist{
ifj == i {
returntrue
}
}
returnfalse
}
//将dis中最小的距离的结点移动至队列最前
funcsorTLiset(list:[NSInteger],graph:[Graph])->[NSInteger]{
vararray = list
varmin = graph.first?.dis
varidx =0
for(i,a)inlist.enumerated(){
ifgraph[a].dis< min!{
min = graph[a].dis
idx = i
}
}
lettemp = list[idx]
array.remove(at: array.index(of:temp)!)
array.insert(temp,at:0)
returnarray
}
funcdisplay(notes:GraphString,begin:Int,end:Int,graph:[Graph]){
varstack = [NSInteger]()//数组容器充当栈先进后出
vargoal = end
whilegoal != begin {
stack.append(goal)
goal = graph[goal].bef
}
stack.append(begin)
print("进过的路为:")
while!stack.isEmpty{
print("-->",notes.cities[stack.removeLast()])
}
print("经过的总长度为：",graph[end].dis)
}
}
以上是算法核心代码 调用代码为
graph.cities= ["1","2","3","4","5","6","7","8","9","10",
"11","12","13","14","15","16","17","18","19","20"]
graph.path=
[[0,-1,-1,-1,-1,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],// 1 - 6
[-1,0,-1,-1,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1],// 2 - 519
[-1,-1,0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1],// 3 - 17
[-1,-1,-1,0,-1,3,-1,3,3,-1,-1,3,-1,-1,3,-1,-1,3,3,-1],// 4 - 6 8 1812 19 15 9
[-1,3,-1,-1,0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3],// 5 -2 20
[3,-1,-1,4,-1,0,-1,-1,-1,-1,3,-1,-1,3,-1,-1,-1,-1,-1,-1],// 6 -1 11 14 4
[-1,-1,-1,-1,-1,-1,0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,3],// 7 - 20
[-1,-1,-1,3,-1,-1,-1,0,-1,-1,3,-1,-1,-1,-1,-1,-1,3,-1,-1],// 8 - 11 18 4
[-1,-1,-1,3,-1,-1,-1,-1,0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],// 9 - 4
[-1,-1,-1,-1,-1,-1,-1,-1,-1,0,-1,-1,-1,-1,-1,3,-1,-1,-1,-1],// 10 - 16
[-1,-1,-1,-1,-1,3,-1,3,-1,-1,0,-1,-1,-1,-1,-1,-1,-1,-1,-1],// 11 - 68
[-1,-1,-1,3,-1,-1,-1,-1,-1,-1,-1,0,-1,-1,-1,-1,-1,3,-1,-1],// 12 - 18 4
[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,-1,3,3,3,-1,-1,-1],// 13 - 15 16 17
[-1,-1,-1,-1,-1,3,-1,-1,-1,-1,-1,-1,-1,0,-1,-1,-1,-1,-1,-1],// 14 - 6
[-1,-1,-1,3,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,0,-1,-1,-1,-1,-1],// 15 - 4 13
[-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,3,-1,-1,0,-1,-1,-1,-1],// 16 - 10 13
[-1,-1,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,3,-1,-1,-1,0,-1,-1,-1],// 17 - 3 13
[-1,-1,-1,3,-1,-1,-1,3,-1,-1,-1,3,-1,-1,-1,-1,-1,0,-1,-1],// 18 - 4 8 12
[-1,3,-1,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,-1],// 19 - 2 4
[-1,-1,-1,-1,3,-1,3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0]]// 20 - 5 7
_=priceIsConsistentAlgorithm(notes:graph, beginIndex:0, endIndex:18)
