Extra Lab Solution

Weighted Graphs and Geo Data

Possible Solution

Helper function for performing BFS
 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
static int *findPathBfs(Graph g, Vertex src, Vertex dest, int max) {
	int *pred = calloc(g->nV, sizeof(int));
	assert(pred != NULL);
	for (Vertex v = 0; v < g->nV; v++) {
		pred[v] = -1;
	}
	pred[src] = src;
	
	Queue q = QueueNew();
	QueueEnqueue(q, src);
	
	bool found = false;
	while (!found && !QueueIsEmpty(q)) {
		Vertex v = QueueDequeue(q);
		
		for (Vertex w = 0; w < g->nV; w++) {
			if (g->edges[v][w] <= max && pred[w] == -1) {
				pred[w] = v;
				if (w == dest) {
					found = true;
					break;
				}
				QueueEnqueue(q, w);
			}
		}
	}
	
	QueueFree(q);
	return pred;
}
findPath
Starting the BFS from src
 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
int findPath(Graph g, Vertex src, Vertex dest, int max, int *path) {
	assert(g != NULL);
	
	int *pred = findPathBfs(g, src, dest, max);
	
	if (pred[dest] == -1) {
		free(pred);
		return 0;
	}
	
	// fill path array in reverse
	int pathLength = 0;
	Vertex curr = dest;
	while (curr != src) {
		path[pathLength++] = curr;
		curr = pred[curr];
	}
	path[pathLength++] = src;
	
	// reverse path array
	for (int i = 0, j = pathLength - 1; i < j; i++, j--) {
		Vertex tmp = path[i];
		path[i] = path[j];
		path[j] = tmp;
	}
	
	free(pred);
	return pathLength;
}
Starting the BFS from dest
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
int findPath(Graph g, Vertex src, Vertex dest, int max, int *path) {
	assert(g != NULL);
	
	int *pred = findPathBfs(g, dest, src, max);
	
	if (pred[src] == -1) {
		free(pred);
		return 0;
	}
	
	int pathLength = 0;
	Vertex curr = src;
	while (curr != dest) {
		path[pathLength++] = curr;
		curr = pred[curr];
	}
	path[pathLength++] = dest;
	
	free(pred);
	return pathLength;
}