Find shortest path between cities

Question

The problem:

You are given a list of cities. Each direct connection between two cities has its transportation cost (an integer bigger than 0). The goal is to find the paths of minimum cost between pairs of cities. Assume that the cost of each path (which is the sum of costs of all direct connections belonging to this path) is at most 200000. The name of a city is a string containing characters a,...,z and is at most 10 characters long.

Input

• s [the number of tests <= 10]

• n [the number of cities <= 10000]

• NAME [city name]

• p [the number of neighbours of city NAME]

• nr cost [nr - index of a city connected to NAME (the index of the first city is 1)] [cost - the transportation cost]

• r [the number of paths to find <= 100]

• NAME1 NAME2 [NAME1 - source, NAME2 - destination]

• [empty line separating the tests]

Output

*cost [the minimum transportation cost from city NAME1 to city NAME2 (one per line)]

Example

Input:

1
4
gdansk
2
2 1
3 3
bydgoszcz
3
1 1
3 1
4 4
torun
3
1 3
2 1
4 1
warszawa
2
2 4
3 1
2
gdansk warszawa
bydgoszcz warszawa

Output:

3
2

Here is my solution in C. But it gets TLE in SPOJ.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include<string.h>


typedef struct edgenode_{    
//----this struct is of dual usage
//----first, it is used as the vertices
//----2nd, it is used as the intermittent structure for holding the addresses
//----of the adjacent vertices of the node
    int dw; //----  weight and distance, depending on usage 
    struct edgenode_ *p;  //---- parent address of the adjacent vertex 
    struct edgenode_ **adj; //----addresses of the adjacent vertices
    char name[100]; //----label

}edgenode;

typedef struct{
//---- whole Graph data structure
    edgenode **V; //----addresses of the nodes
    int nVertices; //----number of vertices
    int nEdges; //----number of edges
}Graph;


void initialize_single_source(Graph*, char*);
void printGraph(Graph*);


#define PARENT(i) ((int)((i)/2)) //---- |_i/2_|
#define LEFT(i) ((i)<<1)      //---- 2i
#define RIGHT(i) (((i)<<1)+1) //---- 2i+1


void build_min_heap(edgenode *a[], int heapsize);
void min_heapify(edgenode *a[], int i, int heapsize);

edgenode* heap_extract_min(edgenode *a[],int heapsize);
  
void build_min_heap(edgenode *a[],int heapsize){

    for(int i = heapsize/2;i>0;i--){
        min_heapify(a, i,heapsize);
    }       
}


void min_heapify(edgenode *a[], int i, int heapsize){
    int l = LEFT(i); //----2i
    int r = RIGHT(i);//----2i+1
    int largest=i;
    edgenode *temp;
    
    
    if (l <= heapsize && a[l]->dw < a[i]->dw){ //----a compare func

        largest = l;
  
    }else{
    
        largest = i;
    }
    
    if (r <= heapsize && a[r]->dw < a[largest]->dw){ 
    
        largest = r;
   
    }

    if (largest != i){
        
        temp = a[i];
        a[i] = a[largest];
        a[largest] = temp;

        min_heapify(a,largest,heapsize);
    }
    
}






bool initialize(Graph *g,char s){

    int n=0,p=0,k=0,cost=0;

//  printf("the number of cities: ");
    scanf("%d",&n);

    if((int)n==0)exit(0);
    
    g->nVertices = n;
    
    g->V = (edgenode**)malloc((g->nVertices+10)*sizeof(edgenode*)); 
    memset(g->V,0,(g->nVertices+10)*sizeof(edgenode*));
    
    for(int i = 1; i <= g->nVertices;i++){
        if((g->V[i] = (edgenode*)malloc(sizeof(edgenode))) == NULL)
            return 0;

    }


    for(int i = 1; i <= g->nVertices;i++){
        char NAME[100];

    //  printf("NAME [city name]: ");
        scanf("%s",NAME);

        strcpy(g->V[i]->name,NAME);

    //  printf("the number of neighbours of city NAME: ");
        scanf("%d",&p);

         g->V[i]->adj = (edgenode**)malloc((p+10)*sizeof(edgenode*)); 
         memset(g->V[i]->adj,0,(p+10)*sizeof(edgenode*));

        for(int j = 1; j <= p;j++){ 
            g->V[i]->adj[j] = (edgenode*)malloc(sizeof(edgenode));
            //printf("city and costs:\n");
            scanf("%d %d",&k,&cost);

            g->V[i]->adj[j]->p = g->V[k];
            g->V[i]->adj[j]->dw = cost;

        }

        g->V[i]->adj[p+1] = (edgenode*)malloc(sizeof(edgenode));
        g->V[i]->adj[p+1]->p = NULL; 

    }
    
    //printGraph(g);

    return 1;
}

void printGraph(Graph *g){
//----prints the graph as a adjacency list representation. 
    for(int i = 1; i <= g->nVertices;i++){
        int j = 1;
        printf("|| %s ||-->",g->V[i]->name);
        while(g->V[i]->adj[j]->p != NULL){
            printf("| %s %d |",g->V[i]->adj[j]->p->name,g->V[i]->adj[j]->dw);
            j++;
        }
    printf("\n\n");   
    }
    printf("\n\n");
}


void initialize_single_source(Graph *g, char *s){
//----names the vertices and sets to a high val 
//----sets the source vertice to 0  

    for(int i = 1; i <= g->nVertices;i++){
        //g->V[i]->name = c[i];

        if((strcmp(g->V[i]->name, s))!=0){
            g->V[i]->p = NULL;
            g->V[i]->dw = 100000001;
        }
        else g->V[i]->dw = 0;

    }

}



void relax(edgenode *a[],int heapsize,edgenode *u,edgenode *v,int w){
    if(v->dw > u->dw + w){
        v->dw = u->dw + w;
        v->p = u;
        build_min_heap(a,heapsize);
    }
    //printf("\t %c %c %d", u->name, v->name, w );
}

edgenode* heap_extract_min(edgenode *a[],int heapsize){

    if(heapsize < 1)
        return NULL;

    edgenode *min = a[1];

    a[1] = a[heapsize];

    heapsize--;
    if(heapsize>0)
    min_heapify(a,1,heapsize);

    return min; 
}

void dijsktra(Graph *g, char *s,char *dest){

    int i ,nv;
    edgenode *u, *v;
    edgenode **set;
    int w;

    initialize_single_source(g, s);

    nv = g->nVertices;

    edgenode  **a;
    
    a = (edgenode**)malloc((g->nVertices+10)*sizeof(edgenode*)); 
    set = (edgenode**)malloc((g->nVertices+10)*sizeof(edgenode*));
    
    for(int i=1;i<=nv;i++){
        a[i]=g->V[i];
    }

    build_min_heap(a,nv);

    i = 1;
    while(nv>0){

        u = heap_extract_min(a,nv);
        nv--;


        set[i] = u;
        int k = 1;
        

        while(u->adj[k]->p != NULL){
            
            
                v = u->adj[k]->p;
                w = u->adj[k]->dw;

                relax(a,nv,u,v,w);               
            
            
            k++;
        }
           
        i++;
    }

    edgenode *shortpath = NULL ;


    for(int i = 1; i<=g->nVertices;i++){

        if(!(strcmp(set[i]->name, dest))){
            shortpath = set[i];
        }
    }



    printf("%d\n",shortpath->dw);
    
    free(a);
    free(set);
}


int main(){
    Graph *g;

    int s,n=1;

//  printf("number of test cases: ");
    scanf("%d",&s);
    if(s==0)exit(0);
    for(int i=1;i<=s;i++){
        g = (Graph*)malloc(sizeof(Graph));
        initialize(g,'s');

        //printf("the number of paths to find: ");
        scanf("%d",&n);

        for(int i=1;i<=n;i++){
            char sombre[100],hombre[100];
            //source,dest
            scanf("%s %s",sombre,hombre);
            dijsktra(g,sombre,hombre);
            
            memset(sombre,0,sizeof(char)*100);
            memset(hombre,0,sizeof(char)*100);
        }

        memset(g,0,sizeof(Graph));

    }

    return 0;
} 

Could anyone suggest some ideas on how to improve its performance?

Answer 1

Code Organization

Function prototypes are very useful in large programs that contain multiple source files, and that in case they will be in header files. In a single file program like this it is better to put the main() function at the bottom of the file and all the functions that get used in the proper order above main(). Keep in mind that every line of code written is another line of code where a bug can crawl into the code.

I was able to delete all the function prototypes and the code had only one error that I corrected by changing the order of the functions min_heapify() and build_min_heap(). When you do have function prototypes, keep them all together; don't insert macro definitions between them.

Self Documenting Code

The LEFT and RIGHT macros are hiding details in the code that forced you to put the same comments in places; this makes the code harder to maintain. It is better to write clear code with meaningful variable and function names, which reduces the need for comments in the code and makes the code easier to write, read, debug and maintain. On of the drawbacks of using macros other than for defining constants is that they are very hard to debug: error messages may not appear on the correct lines.

I would rewrite min_heapify() this way:

void min_heapify(edgenode* a[], int i, int heapsize) {
    int left = i * 2;
    int right = (i * 2) + 1;
    int largest = i;
    edgenode* temp;

    if (left <= heapsize && a[left]->dw < a[i]->dw) { //----a compare func
        largest = left;
    }
    else {
        largest = i;
    }

    if (right <= heapsize && a[right]->dw < a[largest]->dw) {
        largest = right;
    }

    if (largest != i) {
        temp = a[i];
        a[i] = a[largest];
        a[largest] = temp;
        min_heapify(a, largest, heapsize);
    }
}

Performance and Recursion

Iterative solutions generally perform better than recursive solutions; part of this is that in an iterative solution the code stays in the same function - so there is no overhead involved with calling a function. Another problem is that recursion burns up system resources such as the stack; some languages have a depth limit for recursion, all machines have a stack that has a limited size.

Test for Possible Memory Allocation Errors

In modern high-level languages such as C++, memory allocation errors throw an exception that the programmer can catch. This is not the case in the C programming language. While it is rare in modern computers because there is so much memory, memory allocation can fail, especially if the code is working in a limited memory application such as embedded control systems. In the C programming language when memory allocation fails, the functions malloc(), calloc() and realloc() return NULL. Referencing any memory address through a NULL pointer results in undefined behavior (UB).

Possible unknown behavior in this case can be a memory page error (in Unix this would be call Segmentation Violation), corrupted data in the program and in very old computers it could even cause the computer to reboot (corruption of the stack pointer).

To prevent this undefined behavior a best practice is to always follow the memory allocation statement with a test that the pointer that was returned is not NULL.

Example of Current Code:

    a = (edgenode**)malloc((g->nVertices + 10) * sizeof(edgenode*));
    set = (edgenode**)malloc((g->nVertices + 10) * sizeof(edgenode*));

Example of Current Code with Test:

    edgenode** a = malloc((sizeof **a) * (g->nVertices + 10));
    if (a == NULL)
    {
        fprintf(stderr, "Malloc failed in dijsktra()");
        exit(EXIT_FAILURE);
    }

    edgenode** set = malloc((sizeof **set) * g->nVertices + 10));
    if (set == NULL)
    {
        fprintf(stderr, "Malloc failed in dijsktra()");
        exit(EXIT_FAILURE);
    }

Convention When Using Memory Allocation in C

As shown in the example above, when using malloc(), calloc() or realloc() in C a common convention is to use sizeof *PTR rather than sizeof (PTR_TYPE). This makes the code easier to maintain and less error-prone, since less editing is required if the type of the pointer changes.

Declare the Variables as Needed

In the original version of C back in the 1970s and 1980s, variables had to be declared at the top of their scope. That is no longer the case, and a recommended programming practice is to declare the variable as needed. In C the language doesn't provide a default initialization of the variable so variables should be initialized as part of the declaration. For readability and maintainability each variable should be declared and initialized on its own line.

Prefer return From main() Over exit()

It is not necessary to call the exit() function from the main(). exit() is only necessary to terminate the program from functions that are not entry points to the program. The return statement in main() always exits the program.