图最短路径

let maxvex = 20
let maxedge = 20
let infinity = 65535
var PathArc:[Int] = [Int](repeating: 0, count: maxvex) //存储最短路径上的顶点坐标
var ShortPathWeightTable:[Int] = [Int](repeating: 0, count: maxvex) //存储起始点到目标点之间经过的各个点的权值
struct MGraph{
    var vexs:[Int]
    var arc:[[Int]]
    var numVertexes:Int
    var numEdges:Int
    init() {
        self.arc = [[Int]](repeating: [Int](repeating: 0, count: maxvex), count: maxvex)
        self.numVertexes = 9
        self.numEdges=16
        self.vexs = [Int](repeating: 0, count: self.numVertexes)
        for i in 0..<self.numVertexes {
            self.vexs[i] = i
        }
        for i in 0..<self.numVertexes {
            for j in 0..<self.numVertexes {
                if (i == j) {
                    self.arc[i][j] = 0
                } else{
                    self.arc[i][j] = infinity
                    self.arc[j][i] = self.arc[i][j]
                }
            }
        }
        self.arc[0][1]=1;
        self.arc[0][2]=5;
        self.arc[1][2]=3;
        self.arc[1][3]=7;
        self.arc[1][4]=5;
        
        self.arc[2][4]=1;
        self.arc[2][5]=7;
        self.arc[3][4]=2;
        self.arc[3][6]=3;
        self.arc[4][5]=3;
        
        self.arc[4][6]=6;
        self.arc[4][7]=9;
        self.arc[5][7]=5;
        self.arc[6][7]=2;
        self.arc[6][8]=7;
        
        self.arc[7][8]=4;
        
        for i in 0..<self.numVertexes {
            for j in 0..<self.numVertexes {
                self.arc[j][i] = self.arc[i][j]
            }
        }
    }

}

func shortestPath_Dijkstra(_ graph:MGraph, _ v0:Int){
    var final:[Int] = [Int](repeating: 0, count: graph.numVertexes)
    for i in 0..<graph.numVertexes {
        ShortPathWeightTable[i] = graph.arc[v0][i] //初始化权值数组为v0所连接的1,2,3,4,5,6,7的权值
    }
    ShortPathWeightTable[0] = 0 //V0到V0自己权值为0
    final[v0] = 1 //V0此时标记为已处理
    PathArc[v0] = -1 //V0到V0的自己的下标不存在的
    
    for _ in 1..<graph.numVertexes {//从接下来第一个点开始
        var k = 0
        var min = infinity //默认最小距离为无限
        for j in 1..<graph.numVertexes {
            if (final[j] != 1 && ShortPathWeightTable[j] < min) {//找到当前已记录最小权值路径的点
                min = ShortPathWeightTable[j]
                k = j
            }
        }
        final[k] = 1 //标记为已处理
        print("k:",k)
        for j in 1..<graph.numVertexes{
            if (final[j] != 1 && graph.arc[k][j] + min < ShortPathWeightTable[j]) {//如果k与j之间的权值+min < 这个最j对应的最小权值则说明k才是最优解
                ShortPathWeightTable[j] = graph.arc[k][j] + min//更新权值表
                PathArc[j] = k//将K的坐标存入数组顶点中
                print("j:", j, "k:", k)
            }
        }
    }
}

func main(){
    let graph = MGraph()
    shortestPath_Dijkstra(graph, 0)
    
    var j = 0
    for i in 1 ..< graph.numVertexes {
        print("v0->v", i)
        j = i
        while (PathArc[j] != -1) {
            print(PathArc[j])
            j = PathArc[j]
        }
    }
    for i in 1..<graph.numVertexes {
        print("v\(graph.vexs[0]) -> v\(graph.vexs[i]) :\(ShortPathWeightTable[i])")
    }
}

main()