shortest-path-BFS.c

shortest-path-BFS.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTICES 100
#define MAX_QUEUE_SIZE 100

//structura pentru elementele din coada
typedef struct {
  int vertex;
  int distance;
} QueueNode;

typedef struct {
  QueueNode data[MAX_QUEUE_SIZE];
  int front, rear;
} Queue;

int graph[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
int n_vertices;

void init_queue(Queue* q) {
  q->front = 0;
  q->rear = 0;
}

int is_queue_empty(Queue *q) {
    return q->front == q->rear;
}

//adaugi un element in coada
void enqueue(Queue *q, int vertex, int distance) {

    if(q->rear < MAX_QUEUE_SIZE) {
      q->data[q->rear].vertex = vertex;
      q->data[q->rear].distance = distance;
      q->rear++;
    }
}

//extragem un element din coada
QueueNode dequeue(Queue *q) {

     QueueNode node = {-1, -1}; //valori default pentru eroare

     if(!is_queue_empty(q)) {
        node = q->data[q->front];
        q->front++;
     }
     return node;
}


int shortest_path_bfs(int start, int end) {

     if(start == end) {
        return 0;
     }

     //verifica daca nodurile sunt valide
     if(start < 0 || start >= n_vertices || end < 0 || end >= n_vertices) {
       printf("Error: invalid nodes (start = %d, end = %d, max = %d)", start, end, n_vertices - 1);
       return -1;
     }

     //declaram o coada
     Queue q;
     init_queue(&q);

     //initializam strucura de date Coada - Queue

     //marcheaza toate nodurile nevizitate
     for(int i = 0; i < n_vertices; ++i) {
         visited[i] = 0;
     }

     //incepe algoritum BFS (Breadth First Search)

     //adauga in coada nodul start si distance 0
     enqueue(&q, start, 0);

     visited[start] = 1;

     printf("Incep BFS de la nodul %d ...\n", start);

     while(!is_queue_empty(&q)) {

         //extragem
         QueueNode current = dequeue(&q);

         if(current.vertex == -1) {
           break;
         }

          printf("Vizitez nodul %d (distanta %d)\n", current.vertex, current.distance);

          //exploreaza toti vecinii nodului current

          for(int neighbor = 0; neighbor < n_vertices; neighbor++) {

              //verifica daca exista muchi si vecinul nu a fost vizitat
              if(graph[current.vertex][neighbor] == 1 && !visited[neighbor]) {

                   //daca am gasit nodul destinatie
                   if(neighbor == end) {
                     printf("Gasit nodul destinatie %d", end);
                     return current.distance + 1;
                   }

                   //marcheaza vecinul ca vizitat si il adaugi in coada
                   visited[neighbor] = 1;
                   enqueue(&q, neighbor, current.distance + 1);
                   printf(" -> Adaug vecinul %d in coada (distance %d)\n", neighbor, current.distance + 1);
              }
          }
     }

     printf("BFS terminat - nu s-a gasit calea\n");

     return -1;
}

//citim graful din fisier
int read_graph_from_file(const char* filename, int *start, int *end) {

    //freopen(filename, "r", stdin);
    FILE *file = fopen(filename, "r");

    if(!file) {
       printf("Eroare: nu se poate deschide fisierul %s", filename);
       return 0;
    }

    if(fscanf(file,"%d %d %d", &n_vertices, start, end) != 3) {
      printf("Eroare: format invalid in fisier");
      fclose(file);
      return 0;
    }


    printf("Numar de noduri: %d\n", n_vertices);
    printf("Caut calea de la nodul %d la nodul %d\n", *start, *end);

    printf("Matricea de adiacenta: \n");

    for(int i = 0; i < n_vertices; ++i) {

       for(int j = 0; j < n_vertices; ++j) {

              if(fscanf(file, "%d", &graph[i][j]) != 1) {
                printf("Eroare: Nu pot citi matricea de adiacenta\n");
                fclose(file);
                return 0;
              }

              printf("%d ", graph[i][j]);
       }

       printf("\n");
    }
}

int main(int argc, char const *argv[]) {

  int start_vertex, end_vertex;

  read_graph_from_file("graph.in", &start_vertex, &end_vertex);

  int distance = shortest_path_bfs(start_vertex, end_vertex);

  printf("\nDistance = %d", distance);
  return 0;
}

/*
graph.in

5 0 4
0 1 1 0 0
1 0 0 1 1
1 0 0 0 1
0 1 0 0 1
0 1 1 1 0

x = 0
y = 4
lengthwise = ?

*/