О кратчайшем k-вершинном пути в ориентированном графе

Abstract

Приводится формулировка задачи смешанного булева линейного программирования для кратчайшего пути, который проходит через заданное количество вершин ориентированного графа. Даны результаты вычислительных экспериментов с программами решения задач дискретного программирования из NEOS-солвера. Обсуждается формулировка задачи для нахождения кратчайшего гамильтонового пути в ориентированном графе.Наводиться формулювання задачі змішаного булевого лінійного програмування для найкоротшого шляху, який проходить через задану кількість вершин орграфа. Наведено результати обчислювальних експериментів з програмами розв'язання задач дискретного програмування з NEOS-солвера. Обговорюється формулювання задачі для знаходження найкоротшого гамільтонового шляху в орієнтованому графі.We present the formulation of the mixed Boolean linear programming problem for the shortest path, which passes through the given number of nodes of the digraph. The results of numerical experiments of solution of discrete programming problems using NEOS-solver are given. We discuss the formulation of the problem for finding the shortest Hamiltonian path in a directed graph.