initial commit

1 files changed, 153 insertions, 0 deletions

diff --git a/comp2521/sna/Dijkstra.c b/comp2521/sna/Dijkstra.c
new file mode 100644
index 0000000..2600690
--- /dev/null
+++ b/comp2521/sna/Dijkstra.c
@@ -0,0 +1,153 @@
+#include "Dijkstra.h"
+
+#include "PQ.h"
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/*
+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
+}
+
+PredNode {
+        Vertex v;
+        struct PredNode *next;
+};
+*/
+
+static void free_pred_list(PredNode *head) {
+    for (PredNode *i = head; i != NULL;) {
+        PredNode *tmp = i->next;
+        free(i);
+        i = tmp;
+    }
+}
+
+static PredNode *add_pred_back(PredNode *head, const Vertex v) {
+    PredNode *ret = calloc(1, sizeof(PredNode));
+    ret->v = v;
+    // Empty Case.
+    if (head == NULL) {
+        return ret;
+    }
+    PredNode *last = head;
+    // Find the last element in the linked list.
+    for (PredNode *i = head->next; i != NULL; i = i->next) {
+        last = i;
+    }
+    last->next = ret;
+    return head;
+}
+
+// Finds the shortest path from src to all other vertices and stores this
+// information in a ShortestPaths struct.
+// However, if there are multiple shortest paths of the same weight, also store
+// such paths as preds.
+ShortestPaths dijkstra(Graph g, Vertex src) {
+
+    // Initialise return struct ret and allocate appropriate memory.
+    ShortestPaths ret;
+    ret.src = src;
+    const int num_nodes = GraphNumVertices(g);
+    ret.numNodes = num_nodes;
+    ret.dist = calloc((unsigned int)num_nodes, sizeof(int));
+    ret.pred = calloc((unsigned int)num_nodes, sizeof(PredNode));
+
+    // Set all distances as INT_MAX to represent infinity, but the src vertex
+    // as 0 to ensure it is chosen first.
+    for (int i = 0; i < num_nodes; ++i) {
+        ret.dist[i] = INT_MAX;
+    }
+    ret.dist[src] = 0;
+
+    // Initialise queue, insert itself in queue and initialise its distance
+    // as 0.
+    PQ queue = PQNew();
+    PQInsert(queue, src, ret.dist[src]);
+
+    // Perform Dijkstra's algorithm by looping through the queue until empty.
+    while (!PQIsEmpty(queue)) {
+        // Dequeue the vertex with the lowest weight.
+        const Vertex vertex = PQDequeue(queue);
+
+        // Loop through all adjacent vertices for the vertex.
+        AdjList adjacents = GraphOutIncident(g, vertex);
+        for (AdjList i = adjacents; i != NULL; i = i->next) {
+            const int v = i->v;
+            const int w = i->weight;
+            const int path = ret.dist[vertex] + w;
+
+            // Inefficient path, continue.
+            if (ret.dist[v] < path) {
+                continue;
+            }
+
+            // Better path than previously discovered. Free the current pred
+            // list and update distance.
+            if (ret.dist[v] > path) {
+                ret.dist[v] = path;
+                PQInsert(queue, v, ret.dist[v]);
+                free_pred_list(ret.pred[v]);
+                ret.pred[v] = NULL;
+            }
+
+            // Update pred list.
+            ret.pred[v] = add_pred_back(ret.pred[v], vertex);
+        }
+    }
+
+    // After performing the algorithm, we must set all INT_MAX distances back
+    // to zero to conform to the spec.
+    for (int i = 0; i < num_nodes; ++i) {
+        if (ret.dist[i] == INT_MAX) {
+            ret.dist[i] = 0;
+        }
+    }
+
+    return ret;
+}
+
+// Prints out the ShortestPaths structure.
+// Does not need to comply with any requirements.
+void showShortestPaths(ShortestPaths sps) {
+    printf("Shortest path\n");
+    printf("\tNumNodes: %d\n", sps.numNodes);
+    printf("\tsrc: %d\n", sps.src);
+    printf("\tdist\n");
+    for (int i = 0; i < sps.numNodes; ++i) {
+        printf("\t\t%d: %d\n", i, sps.dist[i]);
+    }
+    printf("\tpred\n");
+    for (int i = 0; i < sps.numNodes; ++i) {
+        printf("\t\t%d\n", i);
+        for (PredNode *j = sps.pred[i]; j != NULL; j = j->next) {
+            printf("\t\t\t%d\n", j->v);
+        }
+    }
+}
+
+// Frees all memory associated with a ShortestPaths structure.
+void freeShortestPaths(ShortestPaths sps) {
+    for (int i = 0; i < sps.numNodes; ++i) {
+        for (PredNode *j = sps.pred[i]; j != NULL;) {
+            PredNode *next = j->next;
+            free(j);
+            j = next;
+        }
+    }
+    free(sps.pred);
+    free(sps.dist);
+}