Dijkstra's Algoritm

很多问题都可以抽象为shortest path in a weighted graph。所以掌握一种shortest path的算法还是很重要的。比如这道面经题目(找P5那道题)我是面经。 这里我们提供一种比较简单方便实现的Dijstra algorithm。不是最优的，还有很多优化空间。

Dijkstra's algorithm的思想是。从start point开始，然后把周围能reach到的点存到Queue里面。然后每次取cost最小的那个point来继续traverse这个graph。遇到的每一个点，先检查是否在Q中，不在的话就加进去，在的话就与Q中的点进行比较，如果cost更小就更新Q里面的cost。然后再取一个最短的出来继续算。这样是可以保证最终start到每一个点的cost最小。

好吧我觉得我没有讲清楚，anyway。我们还是看代码吧，我的Q可以用hashed priority queue进行优化。这里我先不管了哈。

class Solution(object):
    def dijkstra(self, graph, start, end):
        D = {}  # distance of the node
        P = {}  # parent of the node
        Q = {}  # Q for get the min
        Q[start] = 0

        while Q:
            v = self.get_min(Q) # get the min vertice
            D[v] = Q[v]
            children = graph[v]
            for c in children:  # relax each child
                dist = Q[v]+children[c]
                if c in D:
                    if dist<D[c]:
                        raise ValueError
                elif c not in Q or dist<Q[c]:
                    Q[c] = dist
                    P[c] = v
            del Q[v]

        path = []
        res = D[end]
        while end in P:
            path.append(end)
            end = P[end]
        path.append(end)

        return path[::-1], res

    def get_min(self, Q):
        m = (None, float('inf'))
        for k in Q:
            if Q[k]<m[1]:
                m = (k, Q[k])
        return m[0]

# example, CLR p.528
G = {'s': {'u':10, 'x':5},
    'u': {'v':1, 'x':2},
    'v': {'y':4},
    'x':{'u':3,'v':9,'y':2},
    'y':{'s':7,'v':6}}

so = Solution()
print so.dijkstra(G, 's', 'v')

另外一种实现方法.

import sys

def min_dist(dist, visited, n):
    min_val = sys.maxint
    min_idx = 0
    for i in xrange(n):
        if not visited[i] and dist[i] <= min_val:
            min_val, min_idx = dist[i], i

    return min_idx

def dijkstra(graph, src, des):
    n = len(graph)
    dist = [sys.maxint] * n
    dist[src] = 0
    visited = [False] * n

    for _ in xrange(n):
        i = min_dist(dist, visited, n)
        visited[i] = True
        if i == des:
           return dist[i]
        for j in xrange(n):
            if (not visited[j] and graph[i][j] and dist[i] != sys.maxint and
                    dist[i] + graph[i][j] < dist[j]):
                dist[j] = dist[i] + graph[i][j]



graph = [[0, 3, 2],[5, 0, 2],[1, 6, 0]]
src, des = 2, 1
print("length of the shortest path from #%d to #%d: %d" \
      % (src, des, dijkstra(graph, src, des)))