0

I have to build a program which takes in the vertices and edges from a csv file and uses an adjacency matrix to store the distance from one vertex to another and calls the function shortest_path which uses the dijkstra's algorithm to find the shortest path and calls the printpath function to print the information of all the vertices it goes through to get from the origin to the end.The information about the vertices is stored in the array of structures arr[]. The problem is that the program stops working when main() call the shortest_path() and the return value is 3221225725

The shortest_path function runs on its own in another program I made but is not called in the main when I execute this program

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_BUFFER 100 
#define MAX_NB 8000
#define INFINITY 9999

typedef struct edges edges;
struct edges{
    int from,to,weight;
};

typedef struct stops stops;
struct stops {
    int id;
    float lat,lont;
    char title[MAX_BUFFER];
};

stops* arr[MAX_NB]={0};

typedef struct Graph{
    int vertices;
//    int visited; 
} Graph; 

int visited[MAX_NB];
int amatrix[MAX_NB][MAX_NB];

    int n;

Graph* create_graph(int num_nodes){
    Graph* g = (Graph *)malloc(sizeof(struct Graph));
    g->vertices=num_nodes;

    int i,j;
    for(i=0;i<num_nodes;i++){
        for(j=0;j<num_nodes;j++){
            amatrix[i][j]=0;
        }
    }
    n=num_nodes;
    return g;
}
Graph *graph;


int next_field( FILE *f, char *buf, int max ) {
    int i=0, end=0, quoted=0;
    
    for(;;) {
        // fetch the next character from file       
        buf[i] = fgetc(f);
        // if we encounter quotes then flip our state and immediately fetch next char
        if(buf[i]=='"') { quoted=!quoted; buf[i] = fgetc(f); }
        // end of field on comma if we're not inside quotes
        if(buf[i]==',' && !quoted) { break; }
        // end record on newline or end of file
        if(feof(f) || buf[i]=='\n') { end=1; break; } 
        // truncate fields that would overflow the buffer
        if( i<max-1 ) { ++i; } 
    }

    buf[i] = 0; // null terminate the string
    return end; // flag stating whether or not this is end of the line
}

void fetch_stops (  FILE *csv, struct stops *p) {
    char buf[MAX_BUFFER];
    
    next_field( csv, buf, MAX_BUFFER );      
    p->id = atoi(buf); 
    next_field( csv, p->title, MAX_BUFFER );
    next_field( csv, buf, MAX_BUFFER );      
    p->lat = atof(buf); 
    next_field( csv, buf, MAX_BUFFER );      
    p->lont = atof(buf); 
}

void fetch_edges (  FILE *csv, struct edges *p) {
    char buf[MAX_BUFFER];
    next_field( csv, buf, MAX_BUFFER );      
    p->from = atoi(buf); 
    next_field( csv, buf, MAX_BUFFER );      
    p->to = atoi(buf); 
    next_field( csv, buf, MAX_BUFFER );      
    p->weight = atoi(buf); 
}

void print_stops( struct stops *p ) {
    printf("%d \t \t %s \t %f  %f\n",
            p->id,p->title, p->lat, p->lont);
}/*
void print_edges( struct edges *p ) {
    printf("%d \t \t %d \t %d\n",
            p->from,p->to, p->weight);
}
*/
int load_vertices(char *fname){
    FILE *f;
    struct stops pArray[MAX_NB];        
    struct stops p;
    f=fopen(fname,"r");
    if(!f) { 
        printf("unable to open file\n"); 
        return 0; 
    }
    fetch_stops( f, &p ); // discard the header data in the first line
    int ngames = 0;
    while(!feof(f)) {
        fetch_stops( f, &pArray[ngames]);
        arr[ngames]=&pArray[ngames];
        ngames++;
    }
    printf("loaded %d vertices\n",ngames);
    fclose(f);
    graph = create_graph(ngames);
    
    return 1;
}

void add_edge(int from, int to, int weight){
    amatrix[from][to]=weight;
    amatrix[to][from]=weight;
}

int load_edges(char *fname/*,Graph *g*/){
    FILE *f;
    struct edges pArray[MAX_NB];
    struct edges p;
    f=fopen(fname,"r");
    if(!f) { 
        printf("unable to open file\n"); 
        return 0; 
    }
    fetch_edges( f, &p ); // discard the header data in the first line
    int nedges = 0;
    int from,to,weight;
    while(!feof(f)) {
    fetch_edges( f, &pArray[nedges]);
    nedges++;
    }
    int i;
    for(i=0;i<nedges;i++){
    add_edge(pArray[i].from,pArray[i].to,pArray[i].weight);
    }
    printf("loaded %d edges\n",nedges);
    fclose(f);
    return 1;
}

void printpath(int parent[], int u){
    // Base Case : If j is source
    if (parent[u] == - 1)
        return;
    printpath(parent, parent[u]);
    printf("%d %s\n", arr[u]->id, arr[u]->title);
}

void shortest_path(int origin, int end){
    printf("Works1");
    int distance[MAX_NB];
    int pred[MAX_NB];
    int cost[MAX_NB][MAX_NB];
    int count,minD,nextn,i,j;
    pred[0]=-1;
    int n=MAX_NB;
    
    printf("Works2");
    for (i = 0; i < n; i++){
    for (j = 0; j < n; j++){
      if (amatrix[i][j] == 0)
        cost[i][j] = INFINITY;
      else
        cost[i][j] = amatrix[i][j];
        }
    }
    for (i = 0; i <n; i++) {
    distance[i] = cost[origin][i];
  }
    printf("Works1");
    distance[origin] = 0;
    printf("Works2");
    visited[origin] = 1;
    count = 1;
    while (count < n - 1) {
        minD = INFINITY;
        for (i = 0; i < n; i++){
            if ((distance[i] < minD) && (visited[i])!=1) {
                minD = distance[i];
                nextn = i;
            }}
        
        visited[nextn] = 1;
    
        for (i = 0; i < n; i++)
            if (!(visited[i]))
                if (minD + cost[nextn][i] < distance[i]) {
                distance[i] = minD + cost[nextn][i];
                pred[i]=nextn;
                }
        count++;
    }
    printf("Works");
    printpath(pred,end);
}

int main () {   
    load_vertices("vertices.csv");
    load_edges("edges.csv")
    printf("%d",amatrix[300][7490]);
    shortest_path(300,253);
    return EXIT_SUCCESS;
}
Kartik Mann
  • 17
  • 1

0 Answers0