#!/usr/bin/env python
# coding=gb2312

# 迪杰斯特拉算法求源点到其余各点的最短路径
"""
算法步骤：

a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。

b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。
"""
import random
import sys

max_int = sys.maxint
max_vertex_num = 100
# 指定点到该点的最短路径
dist = [0 for k in range(max_vertex_num)]
# 保存前驱顶点
prev = [0 for k in range(max_vertex_num)]
# 图的邻接矩阵
matrix = [([0] * max_vertex_num) for i in range(max_vertex_num)]
# matrix = [[0, 6, 3, max_int, max_int, max_int],
#           [6, 0, 2, 5, max_int, max_int],
#           [3, 2, 0, 3, 4, max_int],
#           [max_int, 5, 3, 0, 2, 3],
#           [max_int, max_int, max_int, 2, 0, 5],
#           [max_int, max_int, max_int, 3, 5, 0]]


# 生成图的邻接矩阵， matrix[i][j]表示有向边的权值，不存在有向边时权值为sys.maxint
def create_point():
    for x in range(max_vertex_num):
        for y in range(x):
            if x == y:
                value = 0
            else:
                value = random.randint(1, 12)
            if value > 10:
                value = max_int
                print(str(value)),
            else:
                print(str(value) + '         '),
            matrix[x][y] = value
            matrix[y][x] = value
        print '\n'


# 源点 o
def dijkstra(o):
    # 标记各点是否在S中
    s = [False for x in range(max_vertex_num)]
    # 初始化 o 点到各顶点的距离，当之间不存在有向边时前驱顶点为-1
    for index in range(max_vertex_num):
        dist[index] = matrix[o][index]
        if dist[index] == max_int:
            prev[index] = -1
        else:
            prev[index] = o
    dist[o] = 0
    s[o] = True
    # 依次将其他各点放入S中
    for index in range(1, max_vertex_num, 1):
        min_dist = max_int
        u = o
        for n in range(max_vertex_num):
            if (not s[n]) and (dist[n] <= min_dist):
                u = n
                min_dist = dist[n]
        # 将U中距离最小的电放入S中
        s[u] = True
        print u
        # 以U为新考虑的中间点，依次更新其他各点的距离
        for n in range(max_vertex_num):
            if (not s[n]) and (matrix[u][n] < max_int):
                if (dist[u] + matrix[u][n]) < dist[n]:
                    dist[n] = dist[u] + matrix[u][n]
                    prev[n] = u
    print dist
    print prev


if __name__ == '__main__':
    create_point()
    dijkstra(0)