Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <assert.h>
- #include "Dijkstra.h"
- #include "PQ.h"
- void clearPredNode (PredNode **AdjList, Vertex v) {
- // If we havent set a pred for that node yet
- if (AdjList[v] == NULL) {
- return;
- }
- PredNode *curr = AdjList[v];
- PredNode *temp = NULL;
- // If there is only 1 node in the linked list
- if (curr->next == NULL) {
- free (curr);
- } else {
- // Freeing the linked list
- temp = curr->next;
- while (temp != NULL) {
- free (curr);
- curr = temp;
- temp = temp->next;
- }
- }
- }
- void addPredNode (PredNode **AdjList, Vertex v, Vertex w) {
- // v = adj->v, w = edge.key
- PredNode *new = malloc (sizeof (AdjList));
- new->v = w;
- new->next = NULL;
- PredNode *curr = AdjList[v];
- // If this is the first node
- if (curr == NULL) {
- curr = new;
- } else {
- // Check if it is already in the list
- if (curr->v == w) {
- return;
- }
- while (curr->next != NULL) {
- curr = curr->next;
- if (curr->v == w) {
- return;
- }
- }
- curr->next = new;
- }
- }
- ShortestPaths dijkstra (Graph g, Vertex src) {
- int max = __INT_MAX__;
- // Initializing shortestpaths structure sp
- ShortestPaths sp;
- sp.numNodes = GraphNumVertices (g);
- sp.src = src;
- // Allocating memory for dist and pred
- sp.dist = malloc (sp.numNodes * sizeof (sp.dist));
- sp.pred = malloc (sp.numNodes * sizeof (PredNode *));
- // Initializing values for pred and dist
- for (int i = 0; i < sp.numNodes; i++) {
- sp.dist[i] = max;
- sp.pred[i] = NULL;
- }
- // Creating empty queue
- // Note that key is vertex and value is dist
- PQ q = PQNew ();
- // Setting dist[src]
- sp.dist[src] = 0;
- // Initializing queue
- for (int j = 0; j < sp.numNodes; j++) {
- ItemPQ newEdge;
- newEdge.key = j;
- newEdge.value = sp.dist[j];
- PQAdd(q, newEdge);
- }
- // While the queue is not empty
- while (PQIsEmpty(q) == false) {
- // Dequeue edge
- ItemPQ edge = PQDequeue (q);
- AdjList adj = GraphOutIncident (g, edge.key);
- // While there are still adjacent nodes
- while (adj != NULL) {
- // Distance holds the distance from src to w
- // If we have not visited w relax along edge
- int distance = sp.dist[edge.key] + adj->weight;
- ////////////DEBUGGING PRINTING//////////////////
- printf ("edge.key: %d\n", edge.key);
- printf ("edge.value: %d\n", edge.value);
- printf ("adj->v: %d\n", adj->v);
- printf ("adj->weight: %d\n", adj->weight);
- printf ("distance: %d\n", distance);
- ////////////////////////////////////////////////
- if (distance == sp.dist[adj->v]) {
- addPredNode (sp.pred, adj->v, edge.key);
- }
- else if (distance < sp.dist[adj->v]) {
- // Updating dist array with our new shortest distance
- sp.dist[adj->v] = distance;
- // Update our pred array with new pred after clearing node
- clearPredNode (sp.pred, adj->v);
- // Update pred array
- addPredNode (sp.pred, adj->v, edge.key);
- // Update the PQ
- ItemPQ updatePQ;
- updatePQ.key = adj->v;
- updatePQ.value = distance;
- PQUpdate (q, updatePQ);
- }
- adj = adj->next;
- }
- }
- PQFree (q);
- return sp;
- }
- void showShortestPaths(ShortestPaths sps) {
- return;
- }
- void freeShortestPaths(ShortestPaths sps) {
- return;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement