diff options
Diffstat (limited to 'comp2521/sna')
| -rw-r--r-- | comp2521/sna/Dijkstra.c | 153 | ||||
| -rw-r--r-- | comp2521/sna/Dijkstra.h | 99 |
2 files changed, 252 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); +} 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); + |