11
\$\begingroup\$

I just implement Dijkstra's algorithm in C99. Can you review my code please? I'm looking for any mistake, performance improvement or coding style errors.

main.c

#include "src/map.h"
#include "src/pathfinder.h"

int main() {
  map *map = init(createTuple_2(11, 11));
  addBegin(map, createTuple_2(1, 1));
  addEnd(map, createTuple_2(10, 10));
  addWall(map, createTuple_2(5, 5));
  addWall(map, createTuple_2(3, 5));
  addWall(map, createTuple_2(4, 5));
  addWall(map, createTuple_2(2, 5));
  addWall(map, createTuple_2(6, 5));
  addWall(map, createTuple_2(7, 5));
  addWall(map, createTuple_2(8, 5));
  addWall(map, createTuple_2(9, 5));
  addWall(map, createTuple_2(2, 5));
  addWall(map, createTuple_2(1, 5));
  addWall(map, createTuple_2(0, 5));
  dijkstra(map);

  print(map, 1);
}

pathfinder.h

#ifndef PATHFINDER_H
#define PATHFINDER_H

#include "map.h"

void dijkstra(map *map);

#endif // PATHFINDER_H

pathfinder.c

#include "pathfinder.h"
#include <stdio.h>

void dijkstra(map *map) {
  map->coord[getIndex(map->length.x, map->begin)].distance = 0; 
  while(!isAllVisited(map)) {
    tuple_2 u = smallestDistance(map);
    if(u.x == -1 || u.y == -1) {
      printf("No path found\n");
      return;
    }
    map->coord[getIndex(map->length.x, u)].isChecked = 1;
    updateNeighborhood(map, u);
  }
  tuple_2 path = map->end;
  while(path.x != map->begin.x || path.y != map->begin.y) {
    path = map->coord[getIndex(map->length.x, path)].coordinateFather;
    map->coord[getIndex(map->length.x, path)].isInThePath = 1;
  }
}

map.h

#ifndef MAP_H
#define MAP_H

static const char CHAR_WALL = '#';
static const char CHAR_NOTWALL = ' ';
static const char CHAR_PATH = '.';
static const char CHAR_BEGIN = '*';
static const char CHAR_END = '*';
static const char CHAR_VERTICAL_BORDER = '|';
static const char CHAR_HORIZONTAL_BORDER = '_';

typedef struct {
  int x;
  int y;
} tuple_2;

typedef struct {
  tuple_2 coordinateFather;
  int isChecked;
  int distance;
  int isPracticable;
  int isInThePath;
} node;



typedef struct {
  node *coord;
  tuple_2 length;
  tuple_2 begin;
  tuple_2 end;
} map;

tuple_2 createTuple_2(int x, int y);
map* init(tuple_2 length);
void initNode(node *node);
void addBegin(map *map, tuple_2 begin);
void addEnd(map *map, tuple_2 end);
void addWall(map *map, tuple_2 coordinate);
int isAllVisited(map *map);
tuple_2 smallestDistance(map *map);
void print(map *map, int printPath);
int getIndex(int lengthX, tuple_2 coordinate);
int inBounds(map *map, tuple_2 coordinate);
void updateNeighborhood(map *map, tuple_2 coordinate);

#endif //MAP_H

map.c

#include "map.h"
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>

tuple_2 createTuple_2(int x, int y) {
  tuple_2 temp;
  temp.x = x;
  temp.y = y;
  return temp;
}

void initNode(node *node) {
  node->coordinateFather = createTuple_2(-1, -1);
  node->isChecked = 0;
  node->distance = INT_MAX;
  node->isPracticable = 1;
  node->isInThePath = 0;
}

map* init(tuple_2 length) {
  if(length.x < 0 || length.y < 0) {
    printf("Invalid length\n");
    return NULL;
  }
  map *map = malloc(sizeof(map));
  map->coord = malloc(length.x * length.y * sizeof(node));
  map->length = length;
  map->begin = createTuple_2(-1, -1);
  map->end = createTuple_2(-1, -1);
  for(int x = 0; x < length.x; ++x) {
    for(int y = 0; y < length.y; ++y) {
      initNode(&(map->coord[x + y * length.x]));
    }
  }
  return map;
}

int getIndex(int lengthX, tuple_2 coordinate) {
  return coordinate.x + coordinate.y * lengthX;
}

void addBegin(map *map, tuple_2 begin) {
  if(!inBounds(map, begin))
  {
    printf("Begin out of bounds\n");
    return;
  }
  map->begin = begin;
}

void addEnd(map *map, tuple_2 end) {
  if(!inBounds(map, end)) {
    printf("End out of bounds\n");
    return;
  }
  map->end = end;
}

void addWall(map *map, tuple_2 coordinate) {
  if(!inBounds(map, coordinate)) {
    printf("Wall out of bounds");
    return;
  }
  map->coord[getIndex(map->length.x, coordinate)].isPracticable = 0;
}

void updateNeighborhood(map *map, tuple_2 coordinate) {
  for(int i = -1; i <= 1; ++i)
  {
    for(int j = -1; j <= 1; ++j)
    {
      tuple_2 neighbor = createTuple_2(coordinate.x + i, coordinate.y + j);
      if(!inBounds(map, neighbor))
        continue;
      if(map->coord[getIndex(map->length.x, neighbor)].isChecked)
        continue;
      int cost = map->coord[getIndex(map->length.x, coordinate)].distance;

      if(!j || !i)
        cost += 10;
      else
        cost += 15; // diagonal

      if(cost < map->coord[getIndex(map->length.x, neighbor)].distance)
      {
        map->coord[getIndex(map->length.x, neighbor)].distance = cost;
        map->coord[getIndex(map->length.x, neighbor)].coordinateFather = coordinate; 
      }
    }
  }
}

int isAllVisited(map *map) {
  for(int x = 0; x < map->length.x; ++x) {
    for(int y = 0; y < map->length.y; ++y) {
      if(map->coord[x + y * map->length.x].isPracticable &&
         !map->coord[x + y * map->length.x].isChecked)
        return 0;
    }
  }
  return 1;
}

tuple_2 smallestDistance(map *map) {
  int min = INT_MAX;
  tuple_2 minCoordinate;
  minCoordinate.x = -1;
  minCoordinate.y = -1;
  for(int x = 0; x < map->length.x; ++x) {
    for(int y = 0; y < map->length.y; ++y) {
      if(!map->coord[x + y * map->length.x].isChecked &&
         map->coord[x + y * map->length.x].isPracticable &&
         map->coord[x + y * map->length.x].distance < min) {
        minCoordinate = createTuple_2(x, y);
      }      
    }
  }
  return minCoordinate;
}

int inBounds(map *map, tuple_2 coordinate) {
  return coordinate.x >= 0 && coordinate.x < map->length.x &&
    coordinate.y >= 0 && coordinate.y < map->length.y;
}

void print(map *map, int printPath) {
  putchar(' ');
  for(int i = 0; i < map->length.x; ++i) {
    putchar(CHAR_HORIZONTAL_BORDER);
  }
  for(int y = 0; y < map->length.y; ++y) {
    putchar('\n');
    putchar(CHAR_VERTICAL_BORDER);
    for(int x = 0; x < map->length.x; ++x) {
      if(x == map->begin.x && y == map->begin.y)
        putchar(CHAR_BEGIN);
      else if(x == map->end.x && y == map->end.y)
        putchar(CHAR_END);
      else {
        if(printPath && map->coord[x + y * map->length.x].isInThePath) {
          putchar(CHAR_PATH);
        } else if (map->coord[x + y * map->length.x].isPracticable) {
          putchar(CHAR_NOTWALL);
        } else {
          putchar(CHAR_WALL);
        }
      }     
    }    
    putchar(CHAR_VERTICAL_BORDER);
  }
  putchar('\n');
  putchar(' ');
  for(int i = 0; i < map->length.x; ++i) {
      putchar(CHAR_HORIZONTAL_BORDER);
  }
  putchar('\n');
}

Output:

 ___________
|           |
| *         |
|  .        |
|   .       |
|    ...... |
|##########.|
|          .|
|          .|
|          .|
|          .|
|          *|
 ___________
\$\endgroup\$
3
  • \$\begingroup\$ Welcome to code review, I hope you get some good answers. \$\endgroup\$ Commented Aug 8, 2016 at 13:53
  • \$\begingroup\$ What I left out of my answer, and what chux and JS1 left out of their answer is that any time you allocate memory using malloc() you should all free the memory at some point so you don't have memory leaks. \$\endgroup\$ Commented Aug 9, 2016 at 12:50
  • \$\begingroup\$ Yes, I see this after posting my code, it is already corrected, thank you. \$\endgroup\$ Commented Aug 10, 2016 at 6:56

3 Answers 3

Reset to default
7
\$\begingroup\$

Generally the variable and function naming is clear and makes the code easier to read. If this program is for a first or second year computer science class it's really very good. If you are new to C programming it is also very good. Having modular programs is always good because it allows reuse of the code and minimizes side effects.

Module Partitioning
There is a software design principle called The Single Responsibility Principle. This principle applies to functions and structs in C and functions and classes in C++, Java and other programming languages. The principle states that a function or struct should be designed to do one thing and only one thing. This makes it easier to read, write, test and debug programs.

Another important software design principle is to reduce coupling between modules and data structures. Coupling should be reduced to make each module of a program as independent as possible to reduce side effects. Decoupling modules allow the addition of features or bug fixing in one module without breaking code in another module. This is why global variables are generally frowned upon, they create tighter coupling.

Here are some general guides to software design.

The way the files are currently partitioned creates a tight coupling between main.c and map.h. The main() function really only needs to know about the functions in pathfinder.h. The map variable only needs to be available in the pathfind.c file,

The map header file contains 7 character constants. This creates the static variables in every file that includes it. The static constants should only be included in the files that use them. The map.c file is the only file that uses these constants so all the static variables should be declared there. Currently these static variables are being defined in all files. If they were not staticly defined the linker would be reporting multiply defined errors.

The function inBounds() should be declared as 

static int inBounds(map *map, tuple_2 coordinate)
{
    ....
}

in map.c since it isn't ever called externally.

It might be good if there was a tuple.h, and a tuple.c to manipulate the tuples, and a node.h and a node.c to handle the nodes. This would allow the reuse of these modules at a later time.

More Meaningful Function and Variable Names
A better name for the init() function might be CreateMap() or ConstructMap(). That is what the function does, it would be a constructor in C++. There could then be an initMap() function that does all the following:

  addBegin(map, createTuple_2(1, 1));
  addEnd(map, createTuple_2(10, 10));
  addWall(map, createTuple_2(5, 5));
  addWall(map, createTuple_2(3, 5));
  addWall(map, createTuple_2(4, 5));
  addWall(map, createTuple_2(2, 5));
  addWall(map, createTuple_2(6, 5));
  addWall(map, createTuple_2(7, 5));
  addWall(map, createTuple_2(8, 5));
  addWall(map, createTuple_2(9, 5));
  addWall(map, createTuple_2(2, 5));
  addWall(map, createTuple_2(1, 5));
  addWall(map, createTuple_2(0, 5));

One thought about the above code, it might be good to create an array of tuples called Wall and have the addWall() function use the array to create the wall.

The main() function
The main() function is fine in this program, however, if the program was more complex all the main() function should do is

  1. Process any arguments (argc and argv).
  2. Set up the environment. This includes setting up any error handling.
  3. Call a function to execute the program.
  4. Handle any errors.

Error Handling
The function init() returns allocated memory. The pointer is never checked to see if it has value before it is used. Witin the init() function there are 2 calls to malloc(). The malloc() function returns NULL when malloc() fails, but the return value is never tested.

There are a number of ways to handle issues like this, in a program such as this one it would be best to report the error and quite the program.

Some changes I would reccommend for main.c are: 

#include <stdio.h>
#include <stdlib.h>   // Defines EXIT_SUCCESS and EXIT_FAILURE
#include "pathfinder.h"

int main(int argc, char *argv[])
{
    int status = EXIT_SUCCESS;
    map *map = init(createTuple(11,11));
    if (map == NULL)
    {
        fprintf(stderr, "Unable to initialize map, exiting program\n");
        return EXIT_FAILURE;
    }

    ...

    int status = dijkstra(map);

    return status;
}

There are a number of printf() calls in the code that seem to be reporting errors. 

    printf("Begin out of bounds\n");
    printf("Invalid length\n");
    printf("End out of bounds\n");
    printf("Wall out of bounds");

There is a special file pointer for reporting errors call stderr that is defined in stdio.h. Anything printed to stderr (standard error) will be immediately output to the console. On some operating systems output printed to stderr appears in read and is easier to see. I would change the printf() calls to fprintf(stderr, "...");.

The functions that have these printf() calls might be changed to return error values to stop processing.

int addBegin(map *map, tuple_2 begin) {
  if(!inBounds(map, begin))
  {
    printf("Begin out of bounds\n");
    return EXIT_FAILURE;
  }
  map->begin = begin;
  return EXIT_SUCCESS;
}

You can find more information on stderr here. You might also want to read about perror() and errno.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you! I changed my code, it looks much cleaner. Question: What is the corresponding integer for EXIT_FAILURE and EXIT_SUCCESS? \$\endgroup\$ Commented Aug 10, 2016 at 7:11
  • \$\begingroup\$ EXIT_SUCCESS is 0. EXIT_FAILURE is 1. it is better to use the macros. \$\endgroup\$ Commented Aug 10, 2016 at 11:46
2
\$\begingroup\$

Small idea concerning allocation:

Rather than allocate to the size of a structure, consider allocating to the size of the de-referenced pointer. It is easier to code, less chance for error, easier to review and maintain.

// map->coord = malloc(length.x * length.y * sizeof(node));
map->coord = malloc(length.x * length.y * sizeof *(map->coord));

Note that the type accepted by malloc() is size_t. It possible that int * int overflows even though mathematically the product fits in size_t. To prevent that, simply re-order. 

// map->coord = malloc(length.x * length.y * sizeof *(map->coord));
map->coord = malloc(sizeof *(map->coord) * length.x * length.y);

Note that other multiplication should be use size_t math. 

// map->coord[x + y * length.x]
map->coord[x + (size_t) 1 * y * length.x ]

For that reason, consider using type size_t for array indexing.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you, just a question, size_t is an alias for unsigned long? \$\endgroup\$ Commented Aug 10, 2016 at 7:05
  • \$\begingroup\$ @V.Collette size_t is not an alias for unsigned long. size_t is the type returned by sizeof. It is some unsigned type. It may be unsigned short, unsigned, unsigned long, unsigned long long or some other unsigned type at least 16 bits. It is commonly the same as unsigned or unsigned long. \$\endgroup\$ Commented Aug 10, 2016 at 13:25
2
\$\begingroup\$

Slower than heap based Dijkstra

Your algorithm is slower than a heap based Dijkstra, because the smallestDistance function searches the entire map for the next location to check. A heap based Dijkstra algorithm would maintain a heap of all unvisited neighbors, so you could just remove the top of the heap to find the nearest neighbor for the next step.

If \$n\$ is the number of nodes on your map, your algorithm runs in \$O(n^2)\$ compared to \$O(n \log n)\$ if you used a heap.

Better algorithms

For your particular problem, the A* algorithm would work better than Dijkstra. The Dijkstra algorithm searches outwards from the starting point in all directions whereas the A* algorithm will search in the direction of the destination. For a map with few obstacles, A* could run in \$O(\sqrt n)\$, or in other words linear with respect to the path length (which is at most \$\sqrt n\$ on a square map with n nodes).

\$\endgroup\$
2
  • \$\begingroup\$ Thank you, could I use the heap from standard library for this? And I already think to implement A*, of course it is faster, but It is not always the best path, so I choose Dijkstra. \$\endgroup\$ Commented Aug 10, 2016 at 6:59
  • \$\begingroup\$ @V.Collette I'm pretty sure that A* will find the optimal path if you code it correctly. \$\endgroup\$ Commented Aug 10, 2016 at 9:57

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.