The graph is an undirected weighted graph (my same old Graph class), so the way I do it is use Dijkstra to calculate and get the maximum shortest distance from one node to all other nodes, and update the max shortest distance each time. The maximum shortest distance among all is the diameter.
public class Diameter { private Graph g; public Diameter(Graph g){ this.g = g; } public double maxShortestDistance(Node n){ g.chooseSource(n); PriorityQueuepq = new PriorityQueue (new NodeComparator()); //Set visited = new HashSet (); pq.offer(n); double maxDist = 0.0; while(!pq.isEmpty()){ Node curr = pq.poll(); for(Node nei : g.neighbors.get(curr)){ double distance = g.getEdge(curr.label, nei.label).weight + curr.dist; if(distance < nei.dist){ pq.remove(nei); nei.dist = distance; pq.offer(nei); maxDist = Math.max(maxDist, distance); } } } return maxDist; } public double diameter(){ double diameter = 0.0; for(Node v : g.vertices.values()){ diameter = Math.max(diameter, maxShortestDistance(v)); } return diameter; } private class NodeComparator implements Comparator { public int compare(Node a, Node b){ if(a.dist - b.dist > 0) return 1; else if (a.dist - b.dist < 0) return -1; return 0; } } }
No comments:
Post a Comment