Как я нахожу кратчайший путь, который покрывает все узлы в направленном циклическом графике?
Вы можете использовать триггер, скажем, для Table1 & amp; написать триггер, если есть какое-либо обновление в триггере вызова таблицы 1, чтобы обновить данные таблицы 2.
он начинается как .. создать или заменить TRIGGER имя-триггера
после вставки или обновления таблицы1
для каждой строки ...
Полный триггер см. ( https://www.tutorialspoint.com/plsql/plsql_triggers.htm )
.
3 ответа
РЕДАКТИРОВАТЬ: Упс, неправильно прочитал вопрос. Спасибо @jfclavette за то, что подобрали это. Старый ответ в конце.
Проблема, которую вы пытаетесь решить, называется Проблема коммивояжера . Существует множество потенциальных решений , но они NP-завершены, поэтому вы не сможете найти решение для больших графов.
Старый ответ:
То, что вы пытаетесь найти, называется обхват графика. Это можно решить, установив расстояния от узла до самого себя до бесконечности и используя алгоритм Флойда-Варшалла . Длина самого короткого цикла от узла i - это просто запись в позиции ii.
Для невзвешенного графика BFS выполнит эту работу. Поскольку в вашем графе есть потенциальный цикл, вам необходимо отслеживать посещаемый узел (вам все равно нужно это сделать для BFS).
Для взвешенного графа можно использовать алгоритм Беллмана – Форда. Он также способен обнаруживать циклы.
В невзвешенном случае: Поиск в ширину . В взвешенном случае: Дейкстры .