最短路径

最短路径问题在计算机和数学领域一直是一个经典问题，而且在其他领域有着广泛的应用：
1.经济领域：社会网络分析
2.运筹学领域
3.机器人与人工智能
4.通信网络
在算法研究上，最短路径是属于动态规划算法。

最短路径问题的具体内容

最短路径问题经常给出图结构，并选取起点和重点，根据这些已知条件找到从起点到终点的最短路径。

图中已知起点为A，终点为G，每条边的距离已知，求A到G的最短距离。
这个图很简单，很容易看出结果：
A，C，F，G 长度为8
A，D，F，G 长度为8

抽象为数学问题后：
假设J(v)表示从点v到下一点的最短距离。
从终点G开始，依次回溯，J(G)=0,J(E)=4,J(F)=1,J(C)=3。。。结果如下：

这一数学迭代过程可以表述为：
1.从点A开始
2.在任意点v上，选择下一个节点w时，使下式成立：
                        min{cost(v,w)+J(w)} for w in all nodes linked with node v

 解法

图的数据结构：字典  Graph = dict()
对于node A，Graph['A'] = [(node1,cost1),(node2,cost2),(note3,cost3),...]
node1,node2,node3等都与node 'A'相连。当然，如果要自建数据类型Node，使用字典存储graph的数据结构时，一定要注意类型Node一定要hashable.即： 
class Node(object):
     '''
     '''
     def __hash__(self):
         return 'aNodeHashAlgorithm'.__hash__()

1.初始化:


M是一个比较大的数。

2.迭代：

(1).n=0

(2).

(3).如果J不再变化，就停止，否则，进行第(2)步。

实例

图文件:graph.txt
问题为：找到node0到node99的最短路径。
内容为： 
node0, node1 0.04, node8 11.11, node14 72.21
node1, node46 1247.25, node6 20.59, node13 64.94
node2, node66 54.18, node31 166.80, node45 1561.45
node3, node20 133.65, node6 2.06, node11 42.43
node4, node75 3706.67, node5 0.73, node7 1.02
node5, node45 1382.97, node7 3.33, node11 34.54
node6, node31 63.17, node9 0.72, node10 13.10
node7, node50 478.14, node9 3.15, node10 5.85
node8, node69 577.91, node11 7.45, node12 3.18
node9, node70 2454.28, node13 4.42, node20 16.53
node10, node89 5352.79, node12 1.87, node16 25.16
node11, node94 4961.32, node18 37.55, node20 65.08
node12, node84 3914.62, node24 34.32, node28 170.04
node13, node60 2135.95, node38 236.33, node40 475.33
node14, node67 1878.96, node16 2.70, node24 38.65
node15, node91 3597.11, node17 1.01, node18 2.57
node16, node36 392.92, node19 3.49, node38 278.71
node17, node76 783.29, node22 24.78, node23 26.45
node18, node91 3363.17, node23 16.23, node28 55.84
node19, node26 20.09, node20 0.24, node28 70.54
node20, node98 3523.33, node24 9.81, node33 145.80
node21, node56 626.04, node28 36.65, node31 27.06
node22, node72 1447.22, node39 136.32, node40 124.22
node23, node52 336.73, node26 2.66, node33 22.37
node24, node66 875.19, node26 1.80, node28 14.25
node25, node70 1343.63, node32 36.58, node35 45.55
node26, node47 135.78, node27 0.01, node42 122.00
node27, node65 480.55, node35 48.10, node43 246.24
node28, node82 2538.18, node34 21.79, node36 15.52
node29, node64 635.52, node32 4.22, node33 12.61
node30, node98 2616.03, node33 5.61, node35 13.95
node31, node98 3350.98, node36 20.44, node44 125.88
node32, node97 2613.92, node34 3.33, node35 1.46
node33, node81 1854.73, node41 3.23, node47 111.54
node34, node73 1075.38, node42 51.52, node48 129.45
node35, node52 17.57, node41 2.09, node50 78.81
node36, node71 1171.60, node54 101.08, node57 260.46
node37, node75 269.97, node38 0.36, node46 80.49
node38, node93 2767.85, node40 1.79, node42 8.78
node39, node50 39.88, node40 0.95, node41 1.34
node40, node75 548.68, node47 28.57, node54 53.46
node41, node53 18.23, node46 0.28, node54 162.24
node42, node59 141.86, node47 10.08, node72 437.49
node43, node98 2984.83, node54 95.06, node60 116.23
node44, node91 807.39, node46 1.56, node47 2.14
node45, node58 79.93, node47 3.68, node49 15.51
node46, node52 22.68, node57 27.50, node67 65.48
node47, node50 2.82, node56 49.31, node61 172.64
node48, node99 2564.12, node59 34.52, node60 66.44
node49, node78 53.79, node50 0.51, node56 10.89
node50, node85 251.76, node53 1.38, node55 20.10
node51, node98 2110.67, node59 23.67, node60 73.79
node52, node94 1471.80, node64 102.41, node66 123.03
node53, node72 22.85, node56 4.33, node67 88.35
node54, node88 967.59, node59 24.30, node73 238.61
node55, node84 86.09, node57 2.13, node64 60.80
node56, node76 197.03, node57 0.02, node61 11.06
node57, node86 701.09, node58 0.46, node60 7.01
node58, node83 556.70, node64 29.85, node65 34.32
node59, node90 820.66, node60 0.72, node71 0.67
node60, node76 48.03, node65 4.76, node67 1.63
node61, node98 1057.59, node63 0.95, node64 4.88
node62, node91 132.23, node64 2.94, node76 38.43
node63, node66 4.43, node72 70.08, node75 56.34
node64, node80 47.73, node65 0.30, node76 11.98
node65, node94 594.93, node66 0.64, node73 33.23
node66, node98 395.63, node68 2.66, node73 37.53
node67, node82 153.53, node68 0.09, node70 0.98
node68, node94 232.10, node70 3.35, node71 1.66
node69, node99 247.80, node70 0.06, node73 8.99
node70, node76 27.18, node72 1.50, node73 8.37
node71, node89 104.50, node74 8.86, node91 284.64
node72, node76 15.32, node84 102.77, node92 133.06
node73, node83 52.22, node76 1.40, node90 243.00
node74, node81 1.07, node76 0.52, node78 8.08
node75, node92 68.53, node76 0.81, node77 1.19
node76, node85 13.18, node77 0.45, node78 2.36
node77, node80 8.94, node78 0.98, node86 64.32
node78, node98 355.90, node81 2.59
node79, node81 0.09, node85 1.45, node91 22.35
node80, node92 121.87, node88 28.78, node98 264.34
node81, node94 99.78, node89 39.52, node92 99.89
node82, node91 47.44, node88 28.05, node93 11.99
node83, node94 114.95, node86 8.75, node88 5.78
node84, node89 19.14, node94 30.41, node98 121.05
node85, node97 94.51, node87 2.66, node89 4.90
node86, node97 85.09
node87, node88 0.21, node91 11.14, node92 21.23
node88, node93 1.31, node91 6.83, node98 6.12
node89, node97 36.97, node99 82.12
node90, node96 23.53, node94 10.47, node99 50.99
node91, node97 22.17
node92, node96 10.83, node97 11.24, node99 34.68
node93, node94 0.19, node97 6.71, node99 32.77
node94, node98 5.91, node96 2.03
node95, node98 6.17, node99 0.27
node96, node98 3.32, node97 0.43, node99 5.87
node97, node98 0.30
node98, node99 0.33
node99,
文件格式为：第一个逗号前面为节点，第一个逗号后面为与这个节点相连的节点和节点间距离。
首先要读入图文件。 
filename = 'graph.txt'
def read_graph(filename):
    graph = {}
    with open(filename,'rb') as f:
        for line in f:
            info = line.split(',')
            print info
            key = info[0]
            key = key.strip()
            graph[key] = []
            if key != 'node99':
                for ele in info[1:]:
                    node,cost = ele.split()
                    node = node.strip()
                    cost = cost.strip()
                    cost  = float(cost)
                    graph[key].append((node,cost))
    return graph
然后，初始化J。 
J = {}    
bigNum = 1e4
for key in graph:   #初始化
    J[key] = bigNum
J['node99'] = 0.0    #终点为零
对J进行更新操作的函数。 
def updateJ(graph,J):
    newJ = {}
    
    for key in graph:
        if key == 'node99':
            newJ['node99'] = 0.0
        else:
            nodes = graph[key]
            newJ[key] = min(node[1]+J[node[0]] for node in nodes)
    return newJ
经过多次迭代，直到J不再变化的时候。这个时候我们就可以直接把最短路径打印出来。 
def printPath(graph,J):
    start = 'node0'
    sum_cost = 0.0
    while start !='node99':
        print(start)
        running_min = 1e4
        for dest,cost in graph[start]:
            cost_of_path = cost + J[dest]
            if cost_of_path<running_min:
                running_min = cost_of_path
                min_cost = cost
                min_dest = dest
        start = min_dest
        sum_cost += min_cost
    
    print('node99\n')
    print('total cost is {0:.2f}'.format(sum_cost))
方法十分简单快捷。
全部代码如下： 
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 18 17:18:32 2015

@author: myjiayan
"""

def read_graph(filename):
    graph = {}
    with open(filename,'rb') as f:
        for line in f:
            info = line.split(',')
            key = info[0]
            key = key.strip()
            graph[key] = []
            if key != 'node99':
                for ele in info[1:]:
                    node,cost = ele.split()
                    node = node.strip()
                    cost = cost.strip()
                    cost  = float(cost)
                    graph[key].append((node,cost))
    return graph

def updateJ(graph,J):
    newJ = {}
    
    for key in graph:
        if key == 'node99':
            newJ['node99'] = 0.0
        else:
            nodes = graph[key]
            newJ[key] = min(node[1]+J[node[0]] for node in nodes)
    return newJ
    
def printPath(graph,J):
    start = 'node0'
    sum_cost = 0.0
    while start !='node99':
        print(start)
        running_min = 1e4
        for dest,cost in graph[start]:
            cost_of_path = cost + J[dest]
            if cost_of_path<running_min:
                running_min = cost_of_path
                min_cost = cost
                min_dest = dest
        start = min_dest
        sum_cost += min_cost
    
    print('node99\n')
    print('total cost is {0:.2f}'.format(sum_cost))
    
                
if __name__ == '__main__':
    filename = r'C:\python-tutorial\graph.txt'
    J = {}
    graph = read_graph(filename)
    bigNum = 1e4
    for key in graph:
        J[key] = bigNum
    J['node99'] = 0.0 
    
    iterTimes = 0
    while True:
        newJ = updateJ(graph,J)
        iterTimes += 1
        if newJ == J:
            break
        else:
            J = newJ
    
    printPath(graph,J)
结果就是：
node0
node8
node11
node18
node23
node33
node41
node53
node56
node57
node60
node67
node70
node73
node76
node85
node87
node88
node93
node94
node96
node97
node98
node99


total cost is 160.55