image.png

求A到G最短距离

解题思路

引入“距离表”，描述起点到图中其他各点的最短距离，开始时是无穷大，从起点开始遍历各顶点，刷新它们的邻接点和起点的最短距离，最后遍历到目标点时，其作为一个顶点的邻节点，起点至顶点的距离已经刷新成了最短距离，加上顶点到该邻接点的距离，就是起点到该点的距离。

代码流程

1，建立A点到各点的最短距离表
2，初始化距离表
3，更新A点到它邻接点距离到距离表
4，刷新距离表
1）遍历每个顶点
2）确认当前顶点没有被处理过
3） 找到当前顶点距A点的最短距离
4）遍历当前顶点的邻接点
5）如果邻节点距离+当前顶点距离A点距离
小于当前邻节点距离A点距离则刷新

代码

#!/user/python/bin
# -*- coding=utf-8 -*-


def get_graph_beeline(graph, start, end):
    visted = []

    # 初始化距离表
    dis_dict = {}
    for point in graph:
        if point != start:
            dis_dict.setdefault(point, float('inf'))

    print 'dis_dict:', dis_dict

    # 刷新起点距离
    dis_dict.update(graph.get(start, {}))
    print 'dis_dict:', dis_dict

    visted.append(start)

    # 遍历每个顶点
    for point in graph:
        if point in visted:
            print "%s in visted, pass" % point
            continue

        # 必须是已经刷新过距离表的点，无穷大的没有意义
        max_dis = dis_dict.get(point, float('inf'))
        if max_dis == float('inf'):
            continue

        print 'vist ', point
        visted.append(point)

        # 遍历当前顶点的邻接点，刷新邻节点的距离表
        for n_point, n_dis in graph.get(point, {}).items():
            # 邻节点距起点最短距离
            n_max_dis = n_dis + max_dis
            # 最短距离小于当前记录的距离则刷新
            if n_max_dis < dis_dict.get(n_point, float('inf')):
                dis_dict.update({n_point: n_max_dis})
    return dis_dict.get(end, float('inf'))



if __name__ == '__main__':
    # 初始化图
    graph = {'A': {'B': 5, 'C': 2},
             'B': {'D': 1, 'E': 6},
             'C': {'D': 6, 'F': 8},
             'D': {'E': 1, 'F': 2},
             'E': {'G': 7},
             'F': {'G': 3},
             }

    start = 'A'
    end = 'G'
    print get_graph_beeline(graph, start, end)