SHARE
TWEET

Untitled

a guest Dec 7th, 2019 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #include "Graph.h"
  5. #include "Queue.h"
  6.  
  7. int shortestDistance(Graph g, int src, int dest) {
  8.     // TODO
  9.     int nV = GraphNumVertices(g);
  10.     int *visited = malloc(sizeof(int) * nV);
  11.     for (int i = 0; i < nV; i++) { visited[i] = -1; }
  12.     visited[src] = src;
  13.     Queue q = QueueNew();
  14.     QueueEnqueue(q, src);
  15.     int len = -1;
  16.    
  17.     while (!QueueIsEmpty(q)) {
  18.         int v = QueueDequeue(q);
  19.         for (int i = 0; i < nV; i++) {
  20.             if (GraphIsAdjacent(g, v, i) && visited[i] == -1) {
  21.                 visited[i] = v;
  22.                 QueueEnqueue(q, i);
  23.             }
  24.         }
  25.     }
  26.    
  27.     if (visited[dest] != -1) {
  28.         len = 0;
  29.         for (int i = dest; i != src; i = visited[i]) {
  30.             len++;
  31.         }
  32.     }
  33.    
  34.     free(visited);
  35.     QueueFree(q);
  36.     return len;
  37. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top