Find shortest path between cities

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

-
n [the number of cities

-
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

-
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
#include
#include
#include

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)0;i--){

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 dw dw) { //----a compare func
        largest = left;
    }
    else {
        largest = i;
    }

    if (right dw 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.

StackExchange Code Review Q#128888, answer score: 2