1 files changed, 99 insertions, 0 deletions
diff --git a/comp2521/sna/Dijkstra.h b/comp2521/sna/Dijkstra.h
new file mode 100644
index 0000000..0c3578b
--- /dev/null
+++ b/comp2521/sna/Dijkstra.h
@@ -0,0 +1,99 @@
+// Dijkstra ADT interface
+// COMP2521 Assignment 2
+
+// Note: You MUST NOT modify this file.
+
+#include <stdbool.h>
+
+#include "Graph.h"
+
+typedef struct PredNode {
+	Vertex v;
+	struct PredNode *next;
+} PredNode;
+
+typedef struct ShortestPaths {
+	int numNodes;    // The number of vertices in the graph
+	
+	Vertex src;      // The source vertex
+	
+	int *dist;       // An  array  of distances from the source vertex -
+	                 // one for each vertex (the distance  from  src  to
+	                 // itself is 0)
+	                 // dist[v] contains the distance from src to v
+	                 
+	PredNode **pred; // An  array  of  predecessor  lists - one for each
+	                 // vertex
+	                 // pred[v] contains the predecessor list for vertex
+	                 // v
+} ShortestPaths;
+
+/**
+ * Finds  all  shortest  paths  from  a given source vertex to all other
+ * vertices as discussed in the lectures.
+ *
+ * This  function  offers  one **additional feature** - if there is more
+ * than one shortest path from the source vertex to  another  vertex,  a
+ * vertex  could  have  multiple predecessors (see spec for an example).
+ * The function must keep track of multiple predecessors for each vertex
+ * (if  they  exist)  by storing the predecessor(s) in the corresponding
+ * linked list for that vertex. This will be discussed in detail in  the
+ * lecture.
+ * 
+ * For  example,  suppose that while finding the shortest paths from the
+ * source vertex 0 to all other vertices, we discovered  that  vertex  1
+ * has two possible predecessors on different shortest paths. 
+ * 
+ * Node 0
+ *   Distance
+ *     0 : X
+ *     1 : 2
+ *     2 : 1
+ *   Preds
+ *     0 : NULL
+ *     1 : [0]->[2]->NULL
+ *     2 : [0]->NULL
+ * 
+ * Node 1
+ *   Distance
+ *     0 : 2
+ *     1 : X
+ *     2 : 3
+ *   Preds
+ *     0 : [1]->NULL
+ *     1 : NULL
+ *     2 : [0]->NULL
+ * 
+ * Node 2
+ *   Distance
+ *     0 : 3
+ *     1 : 1
+ *     2 : X
+ *   Preds
+ *     0 : [1]->NULL
+ *     1 : [2]->NULL
+ *     2 : NULL
+ * 
+ * The  function  returns  a 'ShortestPaths' structure with the required
+ * information:
+ * - the number of vertices in the graph
+ * - the source vertex
+ * - distance array
+ * - array of predecessor lists
+ */
+ShortestPaths dijkstra(Graph g, Vertex src);
+
+/**
+ * This  function  is  for  you to print out the ShortestPaths structure
+ * while you are debugging/testing your implementation. 
+ * 
+ * We  will  not call this function during testing, so you may print out
+ * the given ShortestPaths structure in whatever format you want.
+ */
+void showShortestPaths(ShortestPaths sps);
+
+/**
+ * Frees all memory associated with the given ShortestPaths structure.
+ */
+void freeShortestPaths(ShortestPaths sps);
+