Dijkstra.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2019/10/14 11:24
# @Author  : tc
# @File    : Dijkstra.py
"""
对任意给出的图G(V,E)和起点S和终点T,如何求从S到T的最短路径
dijkstra算法:
图G(V,E)设置集合S,存放已被访问的顶点,然后每次从集合V-S中选择与起点s的最短距离最小的一个顶点(记为u),访问并加入集合S。之后,令顶点u为
中介点,优化起点s与所有从u能到达的顶点v之间的最短距离。这样的操作执行n次(n为顶点个数),直到集合S已包含所有顶点。
用来解决单源最短路径,给定图G和起点s

dijkstra算法的策略实现:
设置集合S存放已被访问的顶点,然后执行n次下面的两个步骤(n为顶点个数):
1.每次从集合V-S(即未访问节点)中选择与起点s的最短距离最小的一个顶点(记为u),访问并加入集合S;
2.之后,令顶点u为中介点,优化起点s与所有从u能到达的顶点v之间的最短距离。

伪代码如下:
//G为图,一般设置成全局变量,数组d为源点到达各点的最短路径长度,s为起点
Dijkstra(G,d[],s):
    初始化;
    for(循环n次){
        u = 使d[u]最小的还未被访问的顶点的标号
        记u已被访问
        for(从u出发所能到达的所有顶点v){
            if(v未被访问 and 以u为中介点使s到顶点v的最短距离d[v]更优){
                优化d[v]
            }
        }
    }

"""