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
>_<|| 我手贱!!这个有问题!绝对有问题!!一般般啦,真的很一般般。还不错哦~小表扬一下!GJ!乃就是新世界的神様了,快去拯救世界吧! (No Ratings Yet)
Loading...

2 人次吐槽

  1. demetrius说道:
    骑着 Google Chrome 2.0.172.39 Google Chrome 2.0.172.39 和 Windows XP Windows XP
    Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US) AppleWebKit/530.5 (KHTML, like Gecko) Chrome/2.0.172.39 Safari/530.5

    囧……还研究算法……乃很有爱嘛……
    咱是对dijkstra算法完全没印象了……即使数据结构上过……嘛?

  2. 52computer说道:
    骑着 Firefox 3.5.2 Firefox 3.5.2 和 Windows XP Windows XP
    Mozilla/5.0 (Windows; U; Windows NT 5.1; zh-CN; rv:1.9.1.2) Gecko/20090729 Firefox/3.5.2

    Dijikstra。。。。前段时间搞cfan的Lieo的编程竞赛还写过。。。。

春菜 对话 相声
双击调戏
双击调戏