// 给定一个有向邻接图，求从原点出发到任意一点的最短距离 注：
采用Dijkstra贪心算法优化版，为了减少建立二维邻接矩阵的空间开销，直接使用顶点的属性。具体关于此算法的解释说明可百度.优化功能：由于正在学习设计模式，所以增加了工厂类，可以在工厂类中指定任一个顶点为原点，求从原点到其它任意一点的最短距离。将各顶点封装成了类，每个实际顶点对应一个point对像，最重要的是类属性中的邻接矩阵。 4.打包代码在此下载： https://download.csdn.net/download/qq_42439742/10744154 import Foundation /// 定义顶点的结构 struct Point { var id:Int //编号 var isYuanDian : Bool //是否原点 var isV:Bool=false //是否属于V阵营。true:属于V阵营； false:属于V-S阵营 var juZhen:[(nextId:Int,juli:Int)] = [] //临接矩阵的数组，规则为[(指向的顶点编号，距离)] init(id:Int,isYuanDian:Bool=false,juZhen:[(nextId:Int,juli:Int)]) { self.id=id self.isYuanDian = isYuanDian self.juZhen=juZhen //如果原点，则自动加入到V阵营。其它顶点在V-S阵营 if isYuanDian == true { isV = true } } } /// 顶点工厂类,在此生成所有顶点 class PointFactory { func createPoints() -> [Point] { var points:[Point]=[] //最终返回的点数组 var tmpJuZhen:[(nextId:Int,juli:Int)] = [] //临时的矩阵数组，用于生成某个点 //1号顶点,默认为原点 tmpJuZhen.append((nextId: 2,juli:2)) tmpJuZhen.append((nextId: 3, juli: 5)) points.append( Point(id: 1, isYuanDian: true, juZhen: tmpJuZhen )) //2号顶点 tmpJuZhen.removeAll() tmpJuZhen.append((nextId: 4,juli:6)) tmpJuZhen.append((nextId: 3, juli: 2)) points.append( Point(id: 2, isYuanDian: false, juZhen: tmpJuZhen )) //3号顶点 tmpJuZhen.removeAll() tmpJuZhen.append((nextId: 4,juli:7)) tmpJuZhen.append((nextId: 5, juli: 1)) points.append( Point(id: 3, isYuanDian: false, juZhen: tmpJuZhen )) //4号顶点 tmpJuZhen.removeAll() tmpJuZhen.append((nextId: 3,juli:2)) tmpJuZhen.append((nextId: 5, juli: 4)) points.append( Point(id: 4, isYuanDian: false, juZhen: tmpJuZhen )) //5号顶点 tmpJuZhen.removeAll() points.append( Point(id: 5, isYuanDian: false, juZhen: tmpJuZhen )) //判断有几个原点，只允许有一个，如果有多个，则保留第一个原点 var i=0 for point in points { if point.isYuanDian { i += 1 } } //没有原点则默认第一个为原点 if i==0 { points[0].isYuanDian = true print("没有原点，默认第一个顶点为原点") } //如果有多个原点，则保留第一个 else if i>1{ var j=0 //记录第一个为原点的下标 for i in 0..<points.count{ if points[i].isYuanDian { j = i break } } for i in (j+1)..<points.count { if points[i].isYuanDian { points[i].isYuanDian = false } } print("有多个原点，默认设置第一个为原点") } return points } } /// 计算最短路径的类 class ZuiDuan { private var points : [Point] //顶点数组 private let number :Int //顶点个数，包含原点 private let wuQiongDa = 10000 //定义无穷大 private var yuanDian = 0//原点的下标编号 private var zuiDuan:[Int] = [] //各个顶点的最短路径数组 private var p:[Int] = [] //顶点的前驱数组 init() { points = PointFactory().createPoints() //生成顶点集合 number = points.count //顶点个数 //先求哪个是顶点 for i in 0..<number { if points[i].isYuanDian { self.yuanDian = i break } } //初始化各个顶点的最短路径数组zuiduan[] for _ in 0..<number { zuiDuan.append(wuQiongDa) //对数组全部用无穷大填充 } //再用原点的下级邻接矩阵填充各顶点的最短路径数组zuiduan[] zuiDuan[yuanDian]=0 for tmpJuZhen in points[yuanDian].juZhen{ //读取原点的邻接矩阵 zuiDuan[tmpJuZhen.nextId-1] = tmpJuZhen.juli } //初始化各顶点的前驱数组 for i in 0..<number{ //如果【0】的值为无穷大，则为-1，表示没有前驱点 if zuiDuan[i] == 0 || zuiDuan[i] == wuQiongDa { p.append(-1) } //如果值不为无穷大，则为1，表示和顶点有边相连，前驱点为顶点 else{ p.append(yuanDian+1) } } } /// 打印邻接矩阵，默认最短路径数组，前驱数组 func prinfJuZhen(){ print("各顶点到原点的最短路径数组：") for juli in zuiDuan { print("\(juli) ") } print("各顶的前驱数组为：") for x in p{ print("\(x)") } } /// 求V-S中到顶点距离最短的点和距离 /// /// - Returns: 返回最短的ID和距离，其中iD为下标，当ID为-1时说明已经没有下级节点 func getVS_ZuiDuan() ->(id:Int,juli:Int) { //再确定离顶点最短的距离和顶点 var min=wuQiongDa //最小的距离,默认为无穷大 var t = -1 //最小的距离对应的顶点下标，如果=-1，说明没有下级节点 //统计V-S中的顶点 --新建VS数组，存放还在V-S中的顶点 var vs:[Point] = [] for i in 0..<points.count{ if points[i].isV == false { vs.append(points[i]) } } //如果V-S为空，代表所有顶点都在V阵营，返回t=-1 if vs.isEmpty { return (t,min) } //当还有顶点在V-S阵营的时侯，求V-S阵营中离原点的最短距离 for i in 0..<vs.count { if min >= zuiDuan[vs[i].id-1] { min = zuiDuan[vs[i].id-1] } } // 求对短距离对应的点 for i in 0..<number { //必须为VS阵营中的顶点 if min == zuiDuan[i] && points[i].isV == false{ t=i break } } return (t,min) } /// 打印结果 func echoResult() { //显示第i+1个顶点的信息 //print("原点为顶点\(yuanDian+1)。。。") for i in 0..<number { var str = "" //最短的路径 if points[i].isYuanDian != true { var x = i //定义最开始的起始点 str = String(i+1) //最后显示的字符串 while p[x] >= 0 { str = str + "->" + String(p[x]) x=p[x]-1 } } if zuiDuan[i] == wuQiongDa { str = "顶点\(i+1)无法到达" } else if zuiDuan[i] == 0{ str = "顶点\(i+1)为原点" } else{ str = "顶点\(i+1)的最短距离为：\(zuiDuan[i]),最短路径为:"+str } print(str) } } /// 计算各个点到顶点的最短路径 /// /// - Returns: func zuiDuanLuJin() { //开始按贪心算法求解。 //1.令V={1},V-S={2,3,4,5}，找V-S中离顶点最近的点 let zuiJin_VS=getVS_ZuiDuan() //如果VS阵营中已经没有顶点了，则显示数据 if zuiJin_VS.id == -1 { //显示结果 // prinfJuZhen() echoResult() return } //更新最短距离数组 let i = zuiJin_VS.id zuiDuan[i] = zuiJin_VS.juli //2.走捷径。与i邻接的点，分别判断最短 //a.通过上一级节点的最短距离。 //b.最短距离数组p[]中已有的值。 //a和b对比，小的就是新的最短距离，重新更新到数组zuiduan[]中，同时更新前驱数组p[] var minJuli=0 //定义一个最短距离的变量 // print("顶点=\(i+1)") for juZhen_item in points[i].juZhen { // print("顶点矩阵为：\(juZhen_item.nextId):\(juZhen_item.juli)") //a.通过上级节点的最短距离 minJuli = zuiDuan[i] + juZhen_item.juli //b.和P【】中的值对比,将比较小的更新到P[]中 if minJuli <= zuiDuan[juZhen_item.nextId-1] { zuiDuan[juZhen_item.nextId-1] = minJuli p[juZhen_item.nextId-1] = i+1 } } //3.将i划入V阵营，重新在V-S阵容中找到顶点最短的 points[i].isV = true //使用递归进行循环 zuiDuanLuJin() } } let zuiduan = ZuiDuan() zuiduan.zuiDuanLuJin() //zuiduan.prinfJuZhen()