Структуры - sergeresko/Lem_in-explanation GitHub Wiki

Я использовал такие структуры:

// generic list
struct List { void *data; List *next; };
​
struct Room {
    char *name; int x, y;
    List *links;                // neighbors: list of pointers to Link
    int distance; Room *parent; // for Dijkstra's algorithm (see Appendix in Bhandari's article)
    Room *pred, *succ;          // pointers to adjacent rooms along the path
};
​
// directed weighted link (FROM the room that has a pointer to this structure TO 'dst')
struct Link { int weight; Room *dst; };
​
struct Graph {
    List *rooms;                // list of pointers to Room
    Room *start, *end;
};

weight — это вес ребра, он бывает равен 1, 0 или -1 (см. алгоритм).

Указатели на структуры Link хранятся списком в поле links каждой комнаты.

Например, для такого графа

A---B---C

содержимое полей links такое:

  • у комнаты A[(1, B)],
  • у комнаты B[(1, A), (1, C)],
  • у комнаты C[(1, B)].

Дальше: Как работает алгоритм