19.python实现图的最短路径-迪杰斯特拉算法

迪杰斯特拉算法

迪杰斯特拉算法(Dijkstra)是经典的最短路径算法，用于计算一个节点到其他节点的最短路径。他的主要特点以起始点为中心向外层层扩散（广度优先搜索思想BFS），直到扩展到终点为止。

迪杰斯特拉算法过程

1. 设置出发顶点为v，顶点集合V(v1,v2,v3…vn)，v到V中其他顶点的距离构成一个集合Dis,Dis(d1,d2,d3…dn)，记录着v到途中其他各个顶点的具体，v到v自身的距离为0，v到v1的距离为di
2. 从Dis中选择最小的di移除Dis集合，移除V集合中对应顶点的vi，此时v到vi的即为最短路径
3. 更新Dis集合，更新规则为 比较v到V集合中顶点的距离值与v通过vi到V集合中顶点的距离值，保留最小值更新到Dis集合中，同时更新顶点v的前驱节点为v1
4. 重复执行直到所有顶点都被访问过

题目

1. 战争时期，胜利乡有 7 个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从 G 点出发，需要分别把邮件分别送到

A, B, C , D, E, F 六个村庄

1. 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5 公里
2. 问：如何计算出 G 村庄到 其它各个村庄的最短距离?
3. 如果从其它点出发到各个点的最短距离又是多少?

class VisitedVertex(object):
    def __init__(self, vertex_num):
        self.visited = [False for i in range(vertex_num)]
        self.dis = [float('inf') for i in range(vertex_num)]
        self.pre = [0 for i in range(vertex_num)]


class DijsktraGraph(object):
    def __init__(self, vertexes, edges):
        self.vertexes = vertexes
        self.edges = edges
        self.vv = VisitedVertex(len(vertexes))

    def dijsktra(self, start):
        """
        使用迪杰斯特拉算法计算某一个点到其他顶点的最短路径
        :param start:
        :return:
        """
        # 标记起始顶点被访问
        self.vv.visited[start] = True
        # 标记起始顶点与自己的距离为0
        self.vv.dis[start] = 0
        self.update(start)
        for i in range(len(self.vertexes)):
            new_index = self.get_new_index()
            self.update(new_index)

    def get_new_index(self):
        """
        当起始顶点访问之后需要找到下一层需要访问的顶点,找到该顶点到其他顶点距离最小的即为目标顶点
        :param index:
        :return:
        """
        min_dis = float('inf')
        index = 0
        for i in range(len(self.vv.visited)):
            if not self.vv.visited[i] and self.vv.dis[i] < min_dis:
                min_dis = self.vv.dis[i]
                index = i
        # 标记已访问
        self.vv.visited[index] = True
        return index

    def update(self, index):
        """
        更新最短距离
        :return: 
        """
        length = 0
        for i in range(len(self.edges[index])):
            # 起始节点 到index的距离 相当于起始节点可能不能直接到达i 节点需要经过index
            dis = self.vv.dis[index]
            # 顶点 index 到 顶点 i的距离
            di = self.edges[index][i]
            # length 含义是 : 出发顶点到index顶点的距离 + 从index顶点到j顶点的距离的和
            length = dis + di
            if not self.vv.visited[i] and 0 < length < self.vv.dis[i]:
                # 更新出发顶点到i的最短距离 和前驱节点
                self.vv.dis[i] = length
                self.vv.pre[i] = index

    def show(self):
        print(self.vv.visited)
        print(self.vv.pre)
        count = 0
        for i in self.vv.dis:
            if i != float('inf'):
                print(self.vertexes[count] + "(%d)" % i)
            else:
                print(self.vertexes[count] + '(N)')
            count += 1


if __name__ == '__main__':
    vertex = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
    N = float('inf')
    mertix = [
        [0, 5, 7, N, N, N, 2],
        [5, 0, N, 9, N, N, 3],
        [7, N, 0, N, 8, N, N],
        [N, 9, N, 0, N, 4, N],
        [N, N, 8, N, 0, 5, 4],
        [N, N, N, 4, 5, 0, 6],
        [2, 3, N, N, 4, 6, 0],
    ]
    dijsktra_graph = DijsktraGraph(vertex, mertix)
    dijsktra_graph.dijsktra(6)
    dijsktra_graph.show()