improve dijkstra lesson material

1 files changed, 89 insertions, 0 deletions

diff --git a/Info/11/NTG/1/Dijkstra/CountPaths/CountPaths.java b/Info/11/NTG/1/Dijkstra/CountPaths/CountPaths.java
new file mode 100644
index 00000000..dd97d4a5
--- /dev/null
+++ b/Info/11/NTG/1/Dijkstra/CountPaths/CountPaths.java
@@ -0,0 +1,89 @@
+import java.util.*;
+class CountPaths {
+	Stack connectionPath = new Stack();
+	List<Stack> connectionPaths = new ArrayList<>();
+
+	static class Node {
+		int id;
+		List<Node> childs;
+
+		Node(int id) {
+			this.id = id;
+			childs = new ArrayList<>();
+		}
+
+		boolean equals(Node other) {
+			return this.id == other.id;
+		}
+
+		List<Node> nextNodes() {
+			return childs;
+		}
+
+		Node addNext(Node next) {
+			childs.add(next);
+			return this;
+		}
+	}
+
+	// See https://stackoverflow.com/questions/9535819/find-all-paths-between-two-graph-nodes
+	void findAllPaths(Node node, Node targetNode) {
+	    for (Node nextNode : node.nextNodes()) {
+	        if (nextNode.equals(targetNode)) {
+	            Stack temp = new Stack();
+	            for (Object node1 : connectionPath)
+	            temp.add(node1);
+	            connectionPaths.add(temp);
+	        } else if (!connectionPath.contains(nextNode)) {
+	            connectionPath.push(nextNode);
+	            findAllPaths(nextNode, targetNode);
+	            connectionPath.pop();
+	        }
+	    }
+	}
+
+	public static void main(String argv[]) {
+		Node v1 = new Node(1);
+		Node v2 = new Node(2);
+		Node v3 = new Node(3);
+		Node v4 = new Node(4);
+		Node v5 = new Node(5);
+		Node v6 = new Node(6);
+		Node v7 = new Node(7);
+		Node v8 = new Node(8);
+		Node v9 = new Node(9);
+		Node v10 = new Node(10);
+		Node v11 = new Node(11);
+		Node v12 = new Node(12);
+		Node v13 = new Node(13);
+		Node v14 = new Node(14);
+		Node v15 = new Node(15);
+		Node v16 = new Node(16);
+
+		v1.addNext(v2);
+		v2.addNext(v1).addNext(v4).addNext(v7);
+		v3.addNext(v4).addNext(v6);
+		v4.addNext(v2).addNext(v3).addNext(v9);
+		v5.addNext(v8).addNext(v14);
+		v6.addNext(v3).addNext(v4).addNext(v9).addNext(v10);
+		v7.addNext(v2).addNext(v9).addNext(v11);
+		v8.addNext(v5).addNext(v11).addNext(v15);
+		v9.addNext(v4).addNext(v6).addNext(v7).addNext(v10).addNext(v11);
+		v10.addNext(v6).addNext(v9).addNext(v11).addNext(v13);
+		v11.addNext(v7).addNext(v8).addNext(v9).addNext(v10).addNext(v12).addNext(v15);
+		v12.addNext(v11).addNext(v13);
+		v13.addNext(v10).addNext(v12).addNext(v16);
+		v14.addNext(v5).addNext(v8);
+		v15.addNext(v11).addNext(v16);
+		v16.addNext(v15).addNext(v13);
+
+
+		CountPaths p = new CountPaths();
+		p.findAllPaths(v13, v2);
+		System.out.println(p.connectionPaths.size());
+
+		p = new CountPaths();
+		p.findAllPaths(v13, v14);
+		System.out.println(p.connectionPaths.size());
+	}
+}