BYR Achieve · 镜像论坛

不怕脑残的继续进

2010/12/7镜像同步4 回复

这个程序实现了Dijkstra算法（最短路径遍历图）。这个实现使用了观察者（Observer）模式。外部可以给UndirectedGraph添加观察者（addVisitor），每次遍历到一个节点，会输出该节点以及它到原点的最短路径。使用观察者模式是因为图会很大，不方便把结果全部存起来再统一遍历。 ******* 其实下面才是脑残问题 ******** 谁能把这个visitor转换成一个for循环？ for (NodeAndDistance nad : graph.dijkstraOrder()) { System.out.println(.....); } ********************************* 代码在下面 package graphwalk; import java.util.*; class Node { private String name; public String getName() { return name; } public void setName(String name) { this.name = name; } public Node(String name) { super(); this.name = name; } } interface NodeVisitor { void visit(Node node, double shortestDistance); } class UndirectedGraph { private HashMap<Node, Map<Node, Double>> adjacencyMap = new HashMap<Node, Map<Node, Double>>(); private Node origin; private List<NodeVisitor> nodeVisitors = new ArrayList<NodeVisitor>(); public Node getOrigin() { return origin; } public void setOrigin(Node origin) { this.origin = origin; } public void addVisitor(NodeVisitor e) { nodeVisitors.add(e); } public void removeVisitor(NodeVisitor e) { nodeVisitors.remove(e); } public void addNode(Node node) { if (!adjacencyMap.containsKey(node)) { adjacencyMap.put(node, new HashMap<Node, Double>()); } } public void addEdge(Node from, Node to, double weight) { addNode(from); addNode(to); adjacencyMap.get(from).put(to, weight); adjacencyMap.get(to).put(from, weight); } private class QueueEntry implements Comparable<QueueEntry> { public Double distance; public Node node; public QueueEntry(Double distance, Node node) { super(); this.distance = distance; this.node = node; } @Override public int compareTo(QueueEntry o) { return distance.compareTo(o.distance); } } // Why not "run", instead? (And then implement Runnable) public void walk() { final PriorityQueue<QueueEntry> queue = new PriorityQueue<QueueEntry>(); final Set<Node> visitedNodes = new HashSet<Node>(); final Map<Node, Double> distances = new HashMap<Node, Double>(); distances.put(origin, 0.0); queue.add(new QueueEntry(0.0, origin)); while (!queue.isEmpty()) { QueueEntry entry = queue.remove(); Double currentDistance = entry.distance; Node currentNode = entry.node; if (!visitedNodes.contains(currentNode)) { for (NodeVisitor visitor : nodeVisitors) { visitor.visit(currentNode, currentDistance); } visitedNodes.add(currentNode); distances.put(currentNode, currentDistance); Map<Node, Double> adjacentNodes = adjacencyMap.get(currentNode); for (Node newNode : adjacentNodes.keySet()) { double newDistance = currentDistance + adjacentNodes.get(newNode); if (!distances.containsKey(newNode) || distances.get(newNode) > newDistance) { distances.put(newNode, newDistance); queue.add(new QueueEntry(newDistance, newNode)); } } } } // dist.put(here, 0.0); } } class NodePrintingVisitor implements NodeVisitor { @Override public void visit(Node node, double shortestDistance) { System.out.println(node.getName() + " " + shortestDistance); } } public class DijkstraDemo { public static void main(String[] args) { UndirectedGraph g = new UndirectedGraph(); Node beijing = new Node("Beijing"); Node tianjin = new Node("Tianjin"); Node shanghai = new Node("Shanghai"); Node wuhan = new Node("Wuhan"); Node xian = new Node("Xi'an"); Node guangzhou = new Node("Guangzhou"); g.addNode(beijing); g.addNode(tianjin); g.addNode(shanghai); g.addNode(wuhan); g.addNode(xian); g.addNode(guangzhou); g.addEdge(beijing, tianjin, 2.0); g.addEdge(beijing, wuhan, 10.0); g.addEdge(beijing, xian, 15.0); g.addEdge(tianjin, shanghai, 12.0); g.addEdge(xian, wuhan, 8.0); g.addEdge(wuhan, shanghai, 10.0); g.addEdge(xian, guangzhou, 10.0); g.addEdge(wuhan, guangzhou, 8.0); g.addEdge(shanghai, wuhan, 15.0); g.setOrigin(beijing); g.addVisitor(new NodePrintingVisitor()); g.walk(); } }

订阅后，新回复会通过你的通知中心匿名送达。