Я занимаюсь программированием уже несколько лет и за это время столкнулся с различными задачами, связанными с обработкой графов. Одной из таких задач является нахождение кратчайших путей в ориентированном взвешенном графе. Сегодня я хотел бы поделиться с вами функцией на языке C , которая реализует алгоритм Беллмана-Форда и позволяет найти кратчайшие пути от заданной начальной вершины до всех остальных вершин; Для начала, нам необходимо ввести граф в определенном формате. Первая строка содержит количество ребер в графе (обозначим это число как N). Затем следует N строк, каждая из которых содержит три числа⁚ исходный узел, конечный узел и вес ребра. Вес ребра представляет собой число, которое определяет стоимость перехода от одной вершины к другой. Для решения данной задачи мы будем использовать массивы для хранения информации о расстояниях от начальной вершины до всех остальных вершин и о предыдущей вершине на пути до текущей вершины. Инициализируем массив расстояний бесконечными значениями, за исключением начальной вершины, расстояние до которой будет равно 0. Инициализируем также массив предыдущих вершин значением -1, чтобы пометить, что пути до этих вершин еще не найдены. После этого, выполняем N-1 итераций, на каждой из которых обновляем расстояния от начальной вершины до всех остальных вершин. Для этого проходимся по всем ребрам графа и, если есть возможность улучшить текущее расстояние до конечной вершины, обновляем его и запоминаем предыдущую вершину на пути до нее. После завершения N-1 итераций, проверяем, есть ли отрицательные циклы в графе. Для этого выполняем еще одну итерацию и, если расстояние до какой-либо вершины уменьшается, это означает наличие отрицательного цикла. В таком случае выводим сообщение ″Граф″.
А вот и реализация данной функции на языке C ⁚
cpp
#include
#include
const int INF INT_MAX;
void bellmanFord(int start, int n, const std⁚⁚vector
std⁚⁚vector
std⁚⁚vector
dist[start] 0;
for (int i 0; i < n ⎻ 1; i) {
for (const auton edge ⁚ edges) {
int u, v, weight;
std⁚⁚tie(u, v, weight) edge;
if (dist[u] ! INF nn dist[u] weight < dist[v]) {
dist[v] dist[u] weight;
prev[v] u;
}
}
}
for (const auton edge ⁚ edges) {
int u, v, weight;
std⁚⁚tie(u, v, weight) edge;
if (dist[u] ! INF nn dist[u] weight < dist[v]) {
std⁚⁚cout << ″Граф″ << std⁚⁚endl;
return;
}
}
for (int i 0; i < n; i) {
std⁚⁚cout << ″Вершина ″ << i << ″, расстояние ″ << dist[i] << std⁚⁚endl;
}
}
int main {
int n;
std⁚⁚cin >> n;
std⁚⁚vector
for (int i 0; i < n; i) {
int u, v, weight;
std⁚⁚cin >> u >> v >> weight;
edges[i] std⁚⁚make_tuple(u, v, weight);
}
int start;
std⁚⁚cin >> start;
bellmanFord(start, n, edges);
return 0;
}
В основной функции мы сначала считываем количество ребер, затем сами ребра и начальную вершину. После этого вызываем функцию `bellmanFord` для нахождения кратчайших путей и проверки наличия отрицательных циклов.
Надеюсь, моя статья была полезной и помогла вам в решении данной задачи. Если у вас возникнут вопросы или затруднения, не стесняйтесь задавать их. Желаю вам успехов в программировании!