Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include "Graph.h"
- #include "Queue.h"
- int shortestDistance(Graph g, int src, int dest) {
- // TODO
- int nV = GraphNumVertices(g);
- int *visited = malloc(sizeof(int) * nV);
- for (int i = 0; i < nV; i++) { visited[i] = -1; }
- visited[src] = src;
- Queue q = QueueNew();
- QueueEnqueue(q, src);
- int len = -1;
- while (!QueueIsEmpty(q)) {
- int v = QueueDequeue(q);
- for (int i = 0; i < nV; i++) {
- if (GraphIsAdjacent(g, v, i) && visited[i] == -1) {
- visited[i] = v;
- QueueEnqueue(q, i);
- }
- }
- }
- if (visited[dest] != -1) {
- len = 0;
- for (int i = dest; i != src; i = visited[i]) {
- len++;
- }
- }
- free(visited);
- QueueFree(q);
- return len;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement