# Time Limit Exceeded with shortest path algorithm

The problem:

SHPATH

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 belongning 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
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);

for(int j = 1; j <= p;j++){
//printf("city and costs:\n");
scanf("%d %d",&k,&cost);

}

}

//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);
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;

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?

• A quick skim tells me your using Dijkstra's Algorithm, likely A* will fit nicely and be much faster. – JavaProphet May 21 '16 at 6:45
• ok. I'll try that – Minar Ashiq Tishan May 21 '16 at 18:21
• How do I approach the heuristics function? I am not using a grid here. – Minar Ashiq Tishan May 22 '16 at 4:16
• Do you know any kind of distance or "how good is is at this point"? Use that. – JavaProphet May 22 '16 at 7:11
• Here is what I have: At first the source node is initialized to 0 others to 100000001( a really big int) . The edges are weighted. At any given node, I know its cumulative distance from the source node yet calculated. How do i proceed from here? – Minar Ashiq Tishan May 22 '16 at 7:32