swift--求源点到各顶点的最短距离

// 给定一个有向邻接图，求从原点出发到任意一点的最短距离
注：

1. 采用Dijkstra贪心算法优化版，为了减少建立二维邻接矩阵的空间开销，直接使用顶点的属性。具体关于此算法的解释说明可百度.
2. 优化功能：由于正在学习设计模式，所以增加了工厂类，可以在工厂类中指定任一个顶点为原点，求从原点到其它任意一点的最短距离。
3. 将各顶点封装成了类，每个实际顶点对应一个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()