第一题：从 节点1 到 节点6 的最短路径

（注：①先创建两个集合，S={ }集合用来装路线确定的，U={ }集合用来装路线未确定的

           ②相邻节点才有权重值，不相邻相当于无限远，用∞表示

           ③每确定一个节点都要更新路线未确定的节点的权重，务必要最小）

第一步：

    S={ 1（0）}

    U={ 2（1），3（12），4（∞），5（∞），6（∞）}

第二步：

    S={ 1（0）， 2（1）}

    U={3（10），4（4），5（∞），6（∞）}

第三步：   

    S={ 1（0）， 2（1），4（4）}

    U={3（8），，5（17），6（19）}

第四步：

    S={ 1（0）， 2（1），4（4），3（8）}

    U={5（13），6（19）}

第五步：

    S={ 1（0）， 2（1），4（4），3（8），5（13）}

    U={6（17）}

第六步：

    S={ 1（0）， 2（1），4（4），3（8），5（13），6（17）}

综上：最短路径就1-->2-->4-->3-->5-->6 最短路径是17

 

第二题：从 节点D 到 节点A 的最短路径

第一步：

    S={ D（0）}

    U={ C（3），E（4），F（∞），B（∞），G（∞），A（∞）}

第二步：

    S={ D（0），C（3）}

    U={ E（4），F（9），B（13），G（∞），A（∞）}

第三步：

    S={ D（0），C（3），E（4）}

    U={ F（6），B（13），G（12），A（∞）}

第四步：

    S={ D（0），C（3），E（4）， F（6）}

    U={B（13），G（12），A（22）}

第五步：

    S={ D（0），C（3），E（4）， F（6），G（12）}

    U={B（13），A（22）}

第六步：

    S={ D（0），C（3），E（4）， F（6），G（12），B（13）}

    U={A（22）}

第七步：

    S={ D（0），C（3），E（4）， F（6），G（12），B（13），A（22）}

综上：最短路径是 D-->C-->E-->F-->G-->B-->A   最短路径是22