Dijkstra算法的某些龌龊实现

最近在研究OSPF路由协议。OSPF中SPF是指Sortest Path First，在求这个最短路径的过程中就用到了Dijkstra算法。很不好意思的是虽然数据结构课上仔细讲过（么？我没去上课几乎，应该讲过吧）但是都忘的差不多了- –

本着内死问Google，外事还问Google的精神我很自然的到Wikipedia上查到了有关资料（喂），想看的自己去点连接看。

然后下面是代码，分别使用Java和Python实现，相关数据结构省略，完整的代码在这里。

    public static <T extends Node> Map<T, Path<T>> shortestPath(Network<T> n, T o) {
        final HashMap<T, Path<T>> ret = new HashMap<T, Path<T>>();
        final HashSet<T> s = new HashSet<T>(n.nodes());
        final HashSet<T> p = new HashSet<T>();
        final ArrayList<Link<T>> links = new ArrayList<Link<T>>(n.links());
        s.remove(o);
        for (T node : s) {
            ret.put(node, new Path<T>(o, node));
        }
        Path<T> minPath = null;
        for (Link<T> link : links) {
            if (link.from().equals(o)) {
                Path path = ret.get(link.to());
                path.totalLen = link.length();
                if (minPath == null || path.totalLen < minPath.totalLen) {
                    minPath = path;
                }
            }
        }
        p.add(minPath.to);
        s.remove(minPath.to);
        while (!s.isEmpty()) {
            //计算新路径，替换原有路径（如果更小）
            for (Link<T> link : links) {
                if (link.from().equals(minPath.to) && s.contains(link.to())) {
                    int newLen = minPath.totalLen + link.length();
                    Path<T> path = ret.get(link.to());
                    if (newLen < path.totalLen) {
                        path.hops.clear();
                        path.hops.addAll(minPath.hops);
                        path.hops.add(minPath.to);
                        path.totalLen = newLen;
                    }
                }
            }
            //求最小路径
            Path newMinPath = null;
            for (T node : s) {
                Path path = ret.get(node);
                if (newMinPath == null || path.totalLen < newMinPath.totalLen) {
                    newMinPath = path;
                }
            }
            minPath = newMinPath;
            p.add(minPath.to);
            s.remove(minPath.to);
        }
        return ret;
    }

然后是很令人崩溃的Python实现，lambda满天飞

def shortest_path(nodes, links, node):
    if node in nodes:
        nodes = filter(lambda(n): n != node, nodes)
    nodes = set(nodes)
    links = set(links)
    paths = dict(map(lambda(n): [n, Path(node, n)], nodes))
    minpath = None;
    for (start, end, len) in filter(lambda(l): l[0] == node, links):
        paths[end].length = len
        if minpath == None or minpath.length > len:
            minpath = paths[end]
    nodes.remove(minpath.end)
    while nodes:
        for (start, end, len) in filter(lambda(l): l[0] == minpath.end and l[1] in nodes and l[2] + minpath.length < paths[l[1]].length, links):
            path = paths[end];
            path.hops = minpath.hops + [start]
            path.length = len + minpath.length
        minpath = reduce(lambda min, node:(min == None or paths[node].length < min.length) and paths[node] or min, nodes, None)
        nodes.remove(minpath.end)
    return paths