#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;
}