图 - 单源最短路径

#!/usr/bin/env python3.3
# -*- coding:utf-8 -*-
# Copyright 2013

'''
单源最短路径：
1）bellman_ford算法：将所有的边进行|V|-1次循环，每次循环对所有边进行松弛操作
2）dijkstra算法：将V-S中顶点按最短路径递增的次序加入到S中，并对邻接边进行松弛操作
'''

def bellman_ford(graph, graph_size, s):
    low_weight = [w for w in graph[0]]
    low_weight[s] = 0
    for repeat in range(1, graph_size):
        for u in range(graph_size):
            for v in range(graph_size):
                # 对每条边进行松弛操作
                if low_weight[u] is not None and graph[u][v] is not None:
                    if low_weight[v] is None or low_weight[v] > low_weight[u] + graph[u][v]:
                        low_weight[v] = low_weight[u] + graph[u][v]
    return low_weight

def dijkstra(graph, graph_size, s):
    visit_set = {s}
    low_weight = [w for w in graph[s]]
    low_weight[s] = 0
    for repeat in range(1, graph_size):
        # 查找最小权值的顶点
        k = None
        for v in range(graph_size):
            if v not in visit_set and low_weight[v] is not None:
                if k is None or low_weight[v] < low_weight[k]:
                    k = v
        # 对邻接边进行松弛操作
        for v in range(graph_size):
            if v not in visit_set and graph[k][v] is not None:
                if low_weight[v] is None or low_weight[v] > low_weight[k] +  graph[k][v]:
                    low_weight[v] = low_weight[k] +  graph[k][v]
        visit_set.add(k)
    return low_weight