fork download
copy 
  1. import java.util.Arrays;
  2. import java.util.HashMap;
  3. import java.util.Map;
  4. import java.util.Map.Entry;
  5. import java.util.TreeSet;
  6. import java.util.stream.Collectors;
  7.  
  8. class Ideone {
  9. 	public static void main(String[] args) {
  10. 		test1();
  11. 		test2();
  12. 	}
  13. 	public static void test1() {
  14. 		Graph graph = new Graph();
  15. 		graph.addEdge(0, 1, 4);
  16. 		graph.addEdge(0, 2, 3);
  17. 		graph.addEdge(1, 2, 1);
  18. 		graph.addEdge(1, 3, 2);
  19. 		graph.addEdge(2, 3, 4);
  20. 		graph.addEdge(3, 4, 2);
  21. 		graph.addEdge(4, 5, 6);
  22. 		graph.startAt(0);
  23. 		System.out.println(graph.getPath(5));
  24. 	}
  25. 	public static void test2() {
  26. 		Graph graph = new Graph();
  27. 		graph.addEdge(0, 1, 4);
  28. 		graph.addEdge(0, 2, 3);
  29. 		graph.addEdge(1, 3, 2);
  30. 		graph.addEdge(1, 2, 5);
  31. 		graph.addEdge(2, 3, 7);
  32. 		graph.addEdge(3, 4, 2);
  33. 		graph.addEdge(4, 0, 4);
  34. 		graph.addEdge(4, 1, 4);
  35. 		graph.addEdge(4, 5, 6);
  36. 		graph.startAt(0);
  37. 		System.out.println(graph.getPath(5));
  38. 	}
  39. }
  40. final class Graph {
  41. 	private static final class Node {
  42. 		final int no;
  43. 		Map<Node, Integer> edges = new HashMap<>();
  44. 		Node[] path;
  45. 		int pathWeight;
  46. 		Node(int no) {
  47. 			this.no = no;
  48. 		}
  49. 	}
  50.  
  51. 	private Map<Integer, Node> nodes = new HashMap<>();
  52.  
  53. 	public void addEdge(int sourceNo, int destinationNo, int weight) {
  54. 		Node source = this.nodes.computeIfAbsent(sourceNo, Node::new);
  55. 		Node dest = this.nodes.computeIfAbsent(destinationNo, Node::new);
  56. 		source.edges.put(dest, weight);
  57. 		dest.edges.put(source, weight);
  58. 	}
  59.  
  60. 	public void startAt(int startNo) {
  61. 		this.nodes.values().forEach(n -> n.path = null);
  62. 		Node source = this.nodes.computeIfAbsent(startNo, Node::new);
  63. 		source.path = new Node[] { source };
  64. 		source.pathWeight = 0;
  65. 		TreeSet<Node> pending = new TreeSet<>((a, b) -> Integer.compare(a.pathWeight, b.pathWeight));
  66. 		pending.add(source);
  67. 		while ((source = pending.pollFirst()) != null) {
  68. 			for (Entry<Node, Integer> edge : source.edges.entrySet()) {
  69. 				Node dest = edge.getKey();
  70. 				int weight = source.pathWeight + edge.getValue();
  71. 				if (dest.path == null || weight < dest.pathWeight
  72. 				                      || (weight == dest.pathWeight && source.path.length + 1 < dest.path.length)) {
  73. 					if (dest.path != null)
  74. 						pending.remove(dest);
  75. 					dest.path = Arrays.copyOf(source.path, source.path.length + 1);
  76. 					dest.path[source.path.length] = dest;
  77. 					dest.pathWeight = weight;
  78. 					pending.add(dest);
  79. 				}
  80. 			}
  81. 		}
  82. 	}
  83.  
  84. 	public String getPath(int endNo) {
  85. 		Node node = this.nodes.get(endNo);
  86. 		return (node == null || node.path == null ? "Unreachable" :
  87. 		        Arrays.stream(node.path).map(n -> String.valueOf(n.no)).collect(Collectors.joining(" - "))
  88. 		        + " (distance: " + node.pathWeight + ")");
  89. 	}
  90. }
Success #stdin #stdout 0.16s 2184192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 - 1 - 3 - 4 - 5 (distance: 14)
0 - 4 - 5 (distance: 10)
https://ideone.com/v8Jo6a
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!