迪傑斯特拉算法(Dijkstra) ES6實作

class Graph{

    constructor(props){
        this.edges = [
            [65535,65535,65535,65535,65535,65535,65535],
            [65535,65535,65535,65535,65535,65535,65535],
            [65535,65535,65535,65535,65535,65535,65535],
            [65535,65535,65535,65535,65535,65535,65535],
            [65535,65535,65535,65535,65535,65535,65535],
            [65535,65535,65535,65535,65535,65535,65535],
            [65535,65535,65535,65535,65535,65535,65535]
        ]
        this.vertexs = ['A','B','C','D','E','F','G']
        this.already_visit = [0,0,0,0,0,0,0]
        this.dis = [65535,65535,65535,65535,65535,65535,65535]
        this.preIndexs = [0,0,0,0,0,0,0]
    }

    createGrap = (preIndex,suffixIndex,value) => {
        this.edges[preIndex][suffixIndex] = value
        this.edges[suffixIndex][preIndex] = value
    }

    createGrapMain = () => {
        // A -> B
        this.createGrap(0,1,5)
        // A -> C
        this.createGrap(0,2,2)
        // A -> G
        this.createGrap(0,6,3)

        // C -> G
        this.createGrap(2,6,4)
        // C -> D
        this.createGrap(2,3,2)

        // G -> B
        this.createGrap(6,1,2)
        // G -> E
        this.createGrap(6,4,5)
        // G -> F
        this.createGrap(6,5,7)
        // G -> D
        this.createGrap(6,3,9)

        // B -> E
        this.createGrap(1,4,3)

        // D -> F
        this.createGrap(3,5,8)

        // E -> F
        this.createGrap(4,5,6)
       
    }

    showGraph = () => {
        this.edges.map((e) => console.log(e.toString()))
    }

    dijkstra = (index) => {
        this.dis[index] = 0
        this.upateDis(index)
        this.already_visit[index] = 1
        for(let j = 1; j < 7;j++){
           this.upateDis(this.selectIndex())
        }

        console.log(this.dis.toString())
        
    }
    /**
     * 
     * @returns 傳回dis中找出最小值的索引
     */
    selectIndex = () => {
        let min = 65535
        let index = 0
        for(let j = 0;j < 7;j++){
            if(this.already_visit[j] == 0  && this.dis[j] < min){
                min = this.dis[j]
                index = j
            }
        }
        this.already_visit[index] = 1
        console.log("selectIndex:",index)
        return index
    }

    upateDis = (index) => {
        for(let j = 0;j < 7;j++){
            if( this.already_visit[j] == 0 && this.dis[j] > this.dis[index] + this.edges[index][j]){
                this.dis[j] = this.dis[index] + this.edges[index][j]
                this.preIndexs[j] = index
            }
        }
    }

}

let g = new Graph()
g.createGrapMain()
//g.showGraph()
g.dijkstra(6)