Привет! Сегодня я расскажу тебе о том, как написать функцию на C для нахождения кратчайших путей в ориентированном взвешенном графе. Алгоритм, который мы будем использовать, называется алгоритмом Беллмана-Форда.
Прежде всего, давай определимся с форматом входных данных. Первая строка будет содержать количество ребер в графе, обозначим его за N. Затем следуют N строк, каждая из которых содержит три числа⁚ исходный узел, конечный узел и вес ребра.Теперь перейдем к формату выходных данных. Наша функция будет выводить для каждой вершины расстояние от начальной вершины до нее. Если в графе есть отрицательный цикл, мы должны вывести сообщение ″Граф″.Начнем с объявления и реализации функции⁚
cpp
#include
#include
void bellmanFord(int startNode, int numEdges, std⁚⁚vector
int numNodes edges.size; // Количество вершин в графе
std⁚⁚vector
distance[startNode] 0; // Расстояние до начальной вершины равно 0
for (int i 0; i < numNodes ⎼ 1; i ) { for (int j 0; j < numEdges; j ) { int u edges[j][0]; int v edges[j][1]; int weight edges[j][2]; if (distance[u] ! INT_MAX nn distance[u] weight < distance[v]) { distance[v] distance[u] weight; } } } // Проверяем наличие отрицательных циклов for (int i 0; i < numEdges; i ) { int u edges[i][0]; int v edges[i][1]; int weight edges[i][2]; if (distance[u] ! INT_MAX nn distance[u] weight < distance[v]) { std⁚⁚cout << ″Граф″ << std⁚⁚endl; return; } } for (int i 0; i < numNodes; i ) { std⁚⁚cout << ″Вершина ″ << i << ″⁚ расстояние ⎼ ″; if (distance[i] INT_MAX) { std⁚⁚cout << ″INF″ << std⁚⁚endl; } else { std⁚⁚cout << distance[i] << std⁚⁚endl; } } } Давай разберем, что мы сделали. В начале объявили функцию `bellmanFord`, которая принимает начальную вершину, количество ребер и вектор `edges`, содержащий все ребра с их весами. Затем мы создаем вектор `distance`, инициализируем его значениями `INT_MAX`, что соответствует бесконечности. Расстояние от начальной вершины до самой себя равно нулю, поэтому `distance[startNode]` устанавливаем в 0. Затем мы выполняем алгоритм Беллмана-Форда, повторяя `numNodes ⎯ 1` раз, где `numNodes` ⎼ количество вершин в графе. Вложенный цикл проходит по каждому ребру и, если текущее расстояние от начальной вершины до `u` плюс вес этого ребра меньше расстояния до `v`, обновляем значение `distance[v]`. После завершения алгоритма мы проверяем наличие отрицательных циклов. Для этого мы просто повторяем вложенный цикл еще раз и, если найдено ребро `u -> v`, для которого `distance[u] weight < distance[v]`, выводим сообщение ″Граф″ и завершаем функцию.Наконец, мы выводим результат для каждой вершины. Если расстояние до вершины равно `INT_MAX`, выводим ″INF″, в противном случае выводим фактическое значение расстояния.Теперь, чтобы использовать эту функцию, давай прочтем данные в заданном формате, передадим их в функцию и получим результат⁚
cpp
#include
#include
int main {
int numEdges;
std⁚⁚cin >> numEdges;
std⁚⁚vector
for (int i 0; i < numEdges; i ) {
std⁚⁚cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
}
int startNode;
std⁚⁚cin >> startNode;
bellmanFord(startNode, numEdges, edges);
return 0;
}
Это пример простой программы, которая считывает данные в заданном формате и вызывает функцию `bellmanFord` с этими данными. Обрати внимание, что мы сначала считываем количество ребер, а затем считываем сами ребра в цикле.
Теперь, когда у нас есть все необходимое, можешь протестировать функцию на своих графах и убедиться, что она работает правильно. Удачи!