1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
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);
}
|
