Интерфейс для решения транспортных задач методом Беллмана-Форда

Интерфейс для решения транспортных задач методом Беллмана-Форда

Простая веб-панель для построения графов и определения наиболее дешевых маршрутов с помощью алгоритма Беллмана-Форда.

Основная информация

Данный проект был выполнен в рамках зачётного задания по предмету "Методы оптимизации экономических процессов" и представляет собой реализацию решения транспортной задачи методом Беллмана-Форда. Для разработки было решено использовать процедурный PHP, так как задача является достаточно простой и не требует построения сложной архитектуры.

Функция для построения кратчайшего маршрута

/**
 *  Построение кратчайшего маршрута с помощью алгоритма Беллмана-Форда.
 *  
 *  @param   integer  $start   [Начальная точка]
 *  @param   integer  $end     [Конечная точка]
 *  @param   array  $edges     [Список рёбер]
 *  @param   array  $points    [Список точек]
 *  @return  array
 */
function getEdgeSearch_BellmanFord($start = 0, $end = 0, $edges = [], $points = [])
{
	$start  = (integer) $start;
	$end    = (integer) $end;
	$edges  = (array) $edges;
	$points = (array) $points;

	$result = [
		'routing' => [],
		'cost' => 0
	];
	
	// Количество вершин.
	$n = count($points);
	
	// Количество рёбер.
	$m = count($edges);
	
	// Начальная точка.
	$v = $start - 1;
	
	// Конечная точка.
	$t = $end - 1;
	
	// Массив расстояний.
	$d = array_fill(0, $n, INF);
	
	// Расстояние от начальной точки равно нулю.
	$d[$v] = 0;
	
	// Массив с предками для каждой вершины.
	$p = array_fill(0, $n, -1);
	
	// Карта маршрутизации.
	$path = [];
	
	for (;;) // Бесконечный цикл.
	{
		// Ни одного решения нету.
		// Если потом после прохода всех рёбер не будет найдено ни одного решения,
		// программа закончит работу.
		$any = FALSE;
		
		// Проходим по каждому ребру.
		for ($j = 0; $j < $m; $j++)
		{
			// Если (в первой итерации) мы наткнулись на стартовое ребро.
			// Если в любой другой итерации мы наткнулись на ребро, до которого построен кратчайший маршрут.
			if ($d[$edges[$j]['a'] - 1] < INF)
			{
				// Если расстояние до конца ребра больше, чем до начала + стоимость ребра, то:
				if ($d[$edges[$j]['b'] - 1] > ($d[$edges[$j]['a'] - 1] + $edges[$j]['cost']))
				{
					// Задаём дистанцию до конца ребра как расстояние до начала ребра + вес текущего ребра.
					$d[$edges[$j]['b'] - 1] = $d[$edges[$j]['a'] - 1] + $edges[$j]['cost'];
					
					// Запоминаем для конца текущего ребра его предка (начало ребра).
					$p[$edges[$j]['b'] - 1] = $edges[$j]['a'] - 1;
					
					// Решение найдено.
					$any = TRUE;
				}
			}
		}
		
		// Если решение так и не было найдено, выходим из бесконечного цикла.
		if (!$any)
		{
			break;
		}
	}
	
	// Если найдено расстояние до конечной точки, формируем маршрут.
	if ($d[$t] != INF)
	{	
		// Проходим по всем предкам для конечной точки маршрута.
		for ($current = $t; $current != -1; $current = $p[$current])
		{
			// Запоминаем опорную точку в карту маршрутизации от X до Y.
			$path[] = $current;
		}
		
		// Разворачиваем карту маршрутизации, так как она была построена в обратном порядке.
		$result['routing'] = array_reverse($path);
		
		// Стоимость маршрута до выбранной точки.
		$result['cost'] = $d[$t];
	}
	
	return $result;
}
Наверх