最近在研究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
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算法完全没印象了……即使数据结构上过……嘛?
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的编程竞赛还写过。。。。