Simple BFS (Dijkstra's algorithm)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355
/*
о чем написать:
- задача о нахождении кратчайшего пути
https://ru.wikipedia.org/wiki/Задача_о_кратчайшем_пути
- представление маршрута в виде взвешенного графа (да и вообще о графах)
- различные представления графа (на входе прога читает вершины и ребра в виде
списка, а в процессе работы хранит граф в виде матрицы смежности,
что удобнее и быстрее)
- краткое описание алгоритмов поиска на графах
https://ru.wikipedia.org/wiki/Задача_о_кратчайшем_пути
- алгоритм дейкстры (поиск в ширину, учитывающий веса ребер графа)
https://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html
*/
/*
что реализовано:
- чтение из файла / консоли
- поиск в ширину с учетом весов графа (алгоритм дейкстры)
что пока не реализовано:
- поиск в глубину
*/
/*
нажми на вкладку input, чтобы редактировать данные ввода
само собой расстояния между вершинами графа написаны от балды
можешь проверить работу поиска, поменяв расстояния или поменяв связи между
вершинами графа
чтобы построить граф можно воспользолваться сервисом типа такого:
http://graphonline.ru/
*/
/*
особенности работы этой проги:
- ввод из файла / консоли унифицирован (т.е. используется одна и таже функция
и один и тот же буфер)
- если файл не найден, то в качестве потока ввода используется stdin
- вначале подается список городов, прога считает их кол-во и записывает
названия в массив строк, и только потом создает матрицу смежности и читает
данные о смежности вершин
- есть проверки на ошибки в введенных данных
*/
#include <stdio.h> // printf, sscanf, fgets, stdin
#include <string.h> // strlen
#include <stdlib.h> // malloc, realloc
#include <limits.h> // константа INT_MAX (макс. значение int)
#define TRUE 1 // в си нет true / false, для удобства определяем их
#define FALSE 0
#define BUFFER_LENGTH 80 // кол-во символов в буфере
#define DEFAULT_DISTANCE 0 // значение, когда между вершинами нет связи
struct Graph {
int vnum; // кол-во вершин в графе
int** matrix; // матрица смежности (если ячейка > 0, то это расстояние)
char** vnames; // имена вершин
};
typedef struct Graph Graph; // чтобы писать Graph вместо struct Graph
// прописываем прототипы функций, чтобы можно было прописать вызов функции
// в коде до того, как эта функция реализована
Graph load_graph(FILE* file, char* buffer);
int min_distance(int* distance, int* processed, int vmin);
void dijkstra_search(Graph graph, int start, int end);
/*
загружает данные из файла, используя предоставленный буфер
возвращает новый граф
*/
Graph load_graph(FILE* file, char* buffer) {
int vnum = 0;
int** matrix = NULL;
char** vnames = NULL;
Graph graph;
// СЧИТЫВАЕМ ИМЕНА ГОРОДОВ (и заодно считаем их кол-во)
printf("Reading: Cities names (format: string)...\n");
// цикл будет продолжаться, пока:
// - fgets не вернет NULL (конец файла или ошибка чтения)
// - в буфер не попадет пустая строка
while (fgets(buffer, BUFFER_LENGTH, file) != NULL && buffer[0] != '\n') {
// избавляемся от символа переноса строки в конце строки buffer
// без этого при выводе имени города оно выведется с переносом
buffer[strlen(buffer) - 1] = '\0';
// перераспределяем память под массив указателей на строки с именами городов
// добавляя место для еще одного указателя
// если до этого память под массив не была выделена, она автоматом выделится
vnames = (char**)realloc(vnames, (vnum + 1) * sizeof(*vnames));
// делаем дубликат строки из буфера, и записываем адрес этого дубликата
// в массив названий городов
vnames[vnum] = strdup(buffer);
printf(" id: %i name: %s\n", vnum, vnames[vnum]);
vnum++;
}
// СОЗДАЕМ ПУСТУЮ МАТРИЦУ СМЕЖНОСТИ (2d массив размером vnum*vnum)
// выделяем память под массив из vnum указателей на массивы
matrix = (int**)malloc(vnum * sizeof(*matrix));
for (int i = 0; i < vnum; i++) {
// для каждого из этих указателей на массивы, выделяем память под массив
// из vnum чисел
matrix[i] = (int*)malloc(vnum * sizeof(**matrix));
for (int j = 0; j < vnum; j++) {
// каждый из массивов чисел заполняем числом по умолчанию
matrix[i][j] = DEFAULT_DISTANCE;
}
}
// СЧИТЫВАЕМ РАССТОЯНИЯ МЕЖДУ ПУНКТАМИ (и заодно заполняем матрицу)
printf("Reading: Paths (format: int int int)...\n");
// цикл будет продолжаться, пока:
// - fgets не вернет NULL (конец файла или ошибка чтения)
// - в буфер не попадет пустая строка
while (fgets(buffer, BUFFER_LENGTH, file) != NULL && buffer[0] != '\n') {
int start, end, distance;
// читаем строку
// sscanf возвращает число корректно считанных переменных
// это число можно использовать для проверки на ошибку ввода
int scan_result = sscanf(buffer, "%i %i %i\n", &start, &end, &distance);
// если sscanf не смогла прочитать все 3 числа, пропускаем эту строку
if (scan_result != 3) {
printf("Error: Expected 3 integer values, got %i. Skipping...\n", scan_result);
continue;
}
// если строка считалась корректно, но id городов выходят за границы
// матрицы, пропускаем эту строку
if (start < 0 || start >= vnum || end < 0 || end >= vnum) {
printf("Error: Each city id must be between 0 and %i. Skipping...\n", vnum - 1);
continue;
}
printf(" %s - %s: %ikm\n", vnames[start], vnames[end], distance);
// строка прошла все проверки на ошибку, заполняем ячейки матрицы
// т.к. граф маршрутов неореинтирован (т.е. каждый путь идет в оба конца),
// матрицу следует заполнять симметрично по диагонали
matrix[start][end] = distance;
matrix[end][start] = distance;
}
printf("Reading: Done\n");
// все данные считаны, теперь просто копируем их в граф
graph.vnum = vnum;
graph.matrix = matrix;
graph.vnames = vnames;
// возвращаем готовый граф
return graph;
}
/*
находит самую близкую к start вершину
*/
int min_distance(int* distance, int* mark, int vmin) {
int min = INT_MAX;
int min_index;
for (int v = 0; v < vmin; v++) {
// ищем вершину, которая еще не была проверена И дистанция до которой
// от start меньше чем бесконечность
if (mark[v] == FALSE && distance[v] <= min) {
min = distance[v];
min_index = v;
}
}
// возвращаем id этой вершины
return min_index;
}
/*
алгоритм дейкстры
ищет кратчайший путь от start всех остальных точек
попутно генерирует массив, в котором указывается родитель для каждой вершины
проходя от end до родителя, родителя родителя, и т д мы можем найти
кратчайший путь от end до start, если он есть
код взят отсюда
http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
*/
void dijkstra_search(Graph graph, int start, int end) {
int vnum = graph.vnum; // делаем локальные копии данных о графе
int** matrix = graph.matrix; // так удобнее
char** vnames = graph.vnames;
int distance[vnum]; // дистанция от start до каждой из вершин
int mark[vnum]; // вершины, которые уже проверены
int parent[vnum]; // родители каждой из вершин
for (int i = 0; i < vnum; i++) {
distance[i] = INT_MAX; // сначала дистанция от start до всех остальных
// точек равна бесконечности
mark[i] = FALSE; // помечаем все вершины как еще не обработанные
parent[i] = -1; // пока не известно у какой вершины какой
// родитель, так что ставим везде -1
}
distance[start] = 0; // дистанция от start до start всегда равна нулю
for (int count = 0; count < vnum - 1; count++) {
// берем вершину U из тех, что еще не были проверены и дистанция до которой
// минимально (в начале возьмется вершина start)
int u = min_distance(distance, mark, vnum);
// отмечаем, что U уже проверена
mark[u] = TRUE;
// обновляем дистанцию от start до всех вершин, смежных с U
for (int v = 0; v < vnum; v++) {
// если вершина V еще не была проверена
// И дистанция от U до V больше нуля (если 0, то связи между ними нет)
// И дистанция от start до U не бесконечна
// И дистанция от start до U + дистанция от U до V меньше,
// чем дистанция от start до V
if (mark[v] == FALSE
&& matrix[u][v] > 0
&& distance[u] != INT_MAX
&& distance[u] + matrix[u][v] < distance[v]
) {
// мы ближайшего потомка U, вершину V
parent[v] = u;
// обновляем дистанцию от start до V
distance[v] = distance[u] + matrix[u][v];
}
}
}
// для этого проходимся по массиву родителей
// берем точку финига, находем её радителя,
// находим родителя родителя, и т.д.
// если наткнемся на start, значит путь найден
// если наткнемся на вершину, у которой нет родителя (-1),
// значит путь нельзя проложить
printf("Trying to find the shortest path from %s to %s...\n", vnames[start], vnames[end]);
int path_found = FALSE;
int v = end;
do {
printf(" id: %i name: %s\n", v, vnames[v]);
// дошли до старта
if (v == start) {
path_found = TRUE;
break;
}
// идем к родителю это точки
v = parent[v];
} while (v != -1);
if (path_found == TRUE) {
printf("Path found!\n");
} else {
printf("Path not found.\n");
}
}
int main() {
Graph graph;
char buffer[BUFFER_LENGTH]; // буфер для хранения строк
FILE* file; // указатель на поток данных
printf("Enter file name (or press enter for console input): \n");
// считываем имя файла из консольного ввода
fgets(buffer, BUFFER_LENGTH, stdin);
// избавляемся от символа переноса строки в конце строки buffer
// без этого fopen не сможет найти файл
buffer[strlen(buffer) - 1] = '\0';
// пытаемся открыть файл по имени
file = fopen(buffer, "r");
// если fopen не смогла открыть файл, она возвращает NULL
if (file == NULL) {
printf("File (%s) not found. Using standard console input.\n", buffer);
// в таком случае в качестве файла используем стандартный поток ввода
// stdin (т.е. ввод из консоли)
file = stdin;
}
// загружаем граф из файла
graph = load_graph(file, buffer);
// ксли кол-во прочитанных вершин в графе равно нулю, выходим.
if (graph.vnum == 0) {
printf("Error: No data was read. Exiting...\n");
exit(0);
}
// предлагаем пользователю ввести желаемый маршрут
printf("Input desired route (format: int int):\n");
// считываем ввод в буфер
fgets(buffer, BUFFER_LENGTH, stdin);
int start, end;
// сканируем 2 числа из буфера
// sscanf вернет число успешно отсканированных переменных
int scan_result = sscanf(buffer, "%i %i\n", &start, &end);
// если sscanf прочитала не 2 переменных, это ошибка. выходим.
if (scan_result != 2) {
printf("Error: Expected 2 integers, got %i. Exiting...\n", scan_result);
exit(0);
}
// если пользователь криво ввел точку старта или точку финиша, выходим
if (start < 0 || start >= graph.vnum || end < 0 || end >= graph.vnum) {
printf("Error: Each city id must be between 0 and %i. Exiting...\n", graph.vnum - 1);
exit(0);
}
// поиск кратчайшего пути
dijkstra_search(graph, start, end);
// если препод спросит, почему не используешь free() чтобы особободить память,
// которая была выделена с помощью malloc(), ответь, что операционная система
// (нормальная) в любом случае сама эту память освободит после выхода из проги
return 0;
}
C
INFO