八月份的时候写了一篇代价一致算法的简单版，今天突然想起来，给最终版上传一下。
直接上代码，里面有写内容用法。 这个代码里 ("1","2",1)这种写法是按照另一个简书作者的来写的。但他的链接已经没了，所以这里上不了，他写的是A*给我带来很大的启发。
classGraphAdjacencyListNote {
vardata:AnyObject
varweightNumber:Int//权值，最小生成树使用
varpreNoteIndex:Int//最小生成树使用, 记录该节点挂在那个链上
varnext:GraphAdjacencyListNote?
varvisited:Bool=false
init(data:AnyObject=""asAnyObject, weightNumber:Int=0, preNoteIndex:Int=0) {
self.data= data
self.weightNumber= weightNumber
self.preNoteIndex= preNoteIndex
}
}
classGraphAdjacencyList {
fileprivatevarrelation:Array<(String,String,Int)>
fileprivatevargraph:Array
fileprivatevarrelationDic:Dictionary
init() {
graph= []
relationDic= [:]
relation= []
}
/// 创建无向图或者有向图
///
/// - parameter notes:图的所有节点
/// - parameter relations:图中节点中的关系
/// - parameter isNotDirection: 边是否有方向
///
/// - returns:
init(notes:Array, relations:Array<(String,String,Int)>, isNotDirection:Bool) {
graph= []
relationDic= [:]
relation= []
createGraph(notes: notes, relation: relations, isNotDirection: isNotDirection)
}
// MARK: - GraphType
funccreateGraph(notes:Array, relation:Array<(String,String,Int)>){
createGraph(notes: notes, relation: relation, isNotDirection:true)
}
// MARK: - GraphType
funccreateGraph(notes:Array, relation:Array<(String,String,Int)>, isNotDirection:Bool){
self.relation= relation
foriin0..
letnote =GraphAdjacencyListNote(data: notes[i]asAnyObject)
graph.append(note)
relationDic[notes[i]as!String] = i
}
foriteminrelation {
guardleti =relationDic[item.0],
letj =relationDic[item.1]else{
continue
}
letweightNumber:Int=Int(item.2asNSNumber)
letnote2 =GraphAdjacencyListNote(data: jasAnyObject, weightNumber: weightNumber,preNoteIndex: i)
note2.next=graph[i].next
graph[i].next= note2
//无向图
ifisNotDirection {
letnote1 =GraphAdjacencyListNote(data: iasAnyObject, weightNumber: weightNumber, preNoteIndex: j)
note1.next=graph[j].next
graph[j].next= note1
}
}
}
funcdisplayGraph() {
displayGraph(graph:graph)
}
funcdisplayGraph(graph:Array) {
foriin0..
varcursor:GraphAdjacencyListNote? = graph[i]
whilecursor !=nil{
cursor = cursor?.next
}
}
}
///MARK: -- 代价一致
//记录每个结点到起始结点的距离信息
classDistanceInfo {
varbef:Int=-1//该结点的直属结点索引
vardistance:Int=LONG_MAX//起始节点到该结点的距离
varisInPath =false//标记该节点是否在已生成的路径上
}
/// - parameter beginIndex: 最短路径的起始结点
/// - parameter endIndex:最短路径的结束结点
funcshortestPathDijkstra(beginIndex:Int, endIndex:Int) ->[AnyObject]{
ifbeginIndex
varlist = [NSInteger]()
// 给数组添加起点
list.append(beginIndex)
vardistanceInfos:Array =initDistanceInfo()
distanceInfos[beginIndex].isInPath=true//标记起始位置
distanceInfos[beginIndex].distance=0//起始最短路径为0
while!list.isEmpty{
list =sorTLiset(list: list,graph: distanceInfos)
letnod = list.removeFirst()//单独拿出最小节点 最小节点移除
distanceInfos[nod].isInPath=true
ifnod == endIndex{returndisplayShortPath(endIndex: endIndex, distanceInfo: distanceInfos)}
//遍历当前索引在邻接链表中所对应的链上的所有节点
distanceInfos =countCurrentNoteAllDistance(index: nod, distanceInfos: distanceInfos)
list.insert(findCurrentMiniDistanceIndex(distanceInfos: distanceInfos),at:0)
}
returndisplayShortPath(endIndex: endIndex, distanceInfo: distanceInfos)
}else{// 非法索引
return[]
}
}
//将dis中最小的距离的结点移动至队列最前
funcsorTLiset(list:[NSInteger],graph:[DistanceInfo])->[NSInteger]{
vararray = list
varmin = graph.first?.distance
varidx =0
for(i,a)inlist.enumerated(){
ifgraph[a].distance< min!{
min = graph[a].distance
idx = i
}
}
lettemp = list[idx]
array.remove(at: array.index(of:temp)!)
array.insert(temp,at:0)
returnarray
}
/// 初始化距离信息数组
///
/// - returns: 返回初始化后的信息数组
privatefuncinitDistanceInfo() ->Array {
vardistanceInfos:Array = []
for_in0..
distanceInfos.append(DistanceInfo())
}
returndistanceInfos
}
/// 输出最短路径信息
///
/// - parameter endIndex:最短路径结束索引
/// - parameter distanceInfo: 存储最短路径的数组
privatefuncdisplayShortPath(endIndex:Int, distanceInfo:Array) ->[AnyObject]{
varpath:Array = []//存储最短路径的数组
//串联最小路径
varindex = endIndex
whileindex !=-1{
path.append(index)
index = distanceInfo[index].bef
}
//将最小路径进行进行逆转
path.reverse()
varidxArray = [AnyObject]()
foriin0..
letindex = path[i]
idxArray.append(self.graph[index].data)
varcorsur =self.graph[index].next
whilecorsur !=nil{
ifInt(corsur?.dataas!NSNumber) == path[i+1] {
break
}
corsur = corsur?.next
}
}
idxArray.append(self.graph[endIndex].data)
returnidxArray
}
/// 计算链接链表数组中某一个索引对应的节点，到该节点所对应链上的每个结点的距离
///
/// - parameter index:邻接链表上链的索引
/// - parameter preIndexsAndDistances: 记录起始节点到每个结点的距离的数组
privatefunccountCurrentNoteAllDistance(index:Int,
distanceInfos:Array) ->Array {
vardistanceInfo = distanceInfos
//遍历当前索引在邻接链表中所对应的链上的所有节点
varlistCursor =self.graph[index].next
whilelistCursor !=nil{
//取出该结点对应的下标
guardletcurrentNoteIndex:Int= listCursor?.dataas!Int?else{
returndistanceInfos
}
//取出当前索引所对应的距离信息
letcurrentDistanceInfo = distanceInfo[currentNoteIndex]
//获取index节点的最短路径
letindexNoteDistance = distanceInfo[index].distance
//计算上个结点到当前节点的路径距离
letdistance:Int= indexNoteDistance + (listCursor?.weightNumber)!
//如果现在的距离比之前记录的距离要小，则更新前面节点的索引以及距离。
ifdistance < currentDistanceInfo.distance{
currentDistanceInfo.bef= index
currentDistanceInfo.distance= distance
distanceInfo[currentNoteIndex] = currentDistanceInfo
}
listCursor = listCursor?.next
}
returndistanceInfo
}
/// 查找那些未被探测的点中最小距离的下标并返回
///
/// - parameter preIndexsAndDistance:每个节点距离起始结点最短距离的集合
///
/// - returns:最小距离的下标
privatefuncfindCurrentMiniDistanceIndex(distanceInfos:Array) ->Int{
//将当前链中的所有结点计算完路径完毕后，找出未到达且最小的那个节点继续下一轮的循环
varminDistace =LONG_MAX
varminIndex =0
foriin0..
letitem = distanceInfos[i]
//该点未探测
if!item.isInPath{
ifitem.distance< minDistace {//找出最短的那个路径
minDistace = item.distance
minIndex = i
}
}
}
returnminIndex
}
}
以上是算法代码
以下是使用代码
letallGraphNote = ["1","2","3","4","5","6","7","8","9","10","11","12","13",
"14","15","16","17","18","19","20","21","22","23","24",
"25","26","27","28","29","30","31","32","33","34","35","36"]
letrelationDirectedGraphA =
[("1","2",1),("2","3",1),("3","4",1),("4","10",1),("10","9",1),("10","11",1),
("11","12",1),("12","13",1),("13","14",1),("13","8",1),("8","7",1),("7","6",1),
("10","15",1),("15","16",1),("16","17",1),("17","18",1),("18","24",1),("24","23",1),
("24","25",1),("25","26",1),("26","27",1),("27","28",1),("27","22",1),("22","21",1),
("21","20",1),("20","19",1),("19","13",1),("24","29",1),("29","30",1),("30","31",1),
("31","32",1),("27","33",1),("34","33",1),("34","35",1),("35","36",1),("5","6",1)]
用法就是 self.shortestPath(beg:起始点, end:终点) 即可 内容可以根据自己的使用来进行
func shortestPath(beg:NSInteger,end:NSInteger){
letgraph = GraphAdjacencyList(notes: allGraphNote,relations: relationDirectedGraphA,isNotDirection:true)
graph.displayGraph()
let v = graph.shortestPathDijkstra(beginIndex:beg, endIndex:end)
if v.count >0{
objArray.append(v)
}else{
print("非法",v)
}
}
网友评论