Создание графа связанного списка из массива структур

Question

, поэтому я пытаюсь сгенерировать граф, используя связанные списки из массива структур. Каждая структура содержит ребро графа, т.е. 2 узла и вес. График является ненаправленным, поэтому существует также ребро от узла 2 до узла 1. Содержимое каждой структуры было отсканировано из текстового файла (если это поможет, я тоже могу загрузить это).

//
struct Edge{
    char node_1[20];
    char node_2[20];
    int weight;
};

\\declaring the array of structures
struct Edges edge[49];

Мне нужно реализовать алгоритм кратчайшего пути, как только это будет завершено, но я застрял на этом шаге какое-то время.

ОБНОВЛЕНИЕ; это текстовый файл, который я отсканировал в

Carlisle    Newcastle   92
Nottingham  Birmingham  77
Leeds       York        39
Glasgow     Edinburgh   74
Moffat      Carlisle    65
Doncaster   Hull        76
Northampton Birmingham  90
Leicester   Lincoln     82
Sheffield   Birmingham  122
Lincoln     Doncaster   63
Sheffield   Doncaster   29
Bristol     Reading     130
Hull        Nottingham  145
Blackpool   Leeds       116
Birmingham  Bristol     139
Manchester  Leeds       64
Carlisle    Blackpool   140
Leicester   Northampton -61
Newcastle   York        135
Glasgow     Moffat      -28
Leicester   Sheffield   100
Carlisle    Liverpool   -30
Birmingham  Manchester  129
Oxford      Bristol     116
Leeds       Hull        89
Edinburgh   Carlisle    154
Nottingham  Sheffield   61
Liverpool   Manchester  56
Carlisle    Glasgow     50
Sheffield   Lincoln     74
York        Doncaster   55
Newcastle   Edinburgh   177
Leeds       Sheffield   53
Northampton Oxford      68
Manchester  Carlisle    20

Answer 1

1 Структура данных для ваших узлов

Например, (один) связанный список:

typedef struct node {
    char name[20];
    struct node* next;
} node;

2 Алгоритм поиска кратчайшего пути

Вы должны выбрать Алгоритм перед реализацией ребер, потому что некоторые из них работают достаточно эффективно или не работают с некоторыми структурами данных.

Поскольку у вас есть отрицательные веса в ваших данных, некоторые общеизвестные, такие как Дейкстра, не возможны. Возможно даже, что ваша программа не найдет решения из-за отрицательных циклов.

Насколько я знаю, Беллман-Форд должен работать.

Финал

Теперь решать вам. Если вы застряли на одном из шагов выше, не стесняйтесь спрашивать.