Нахождение второго минимального расстояния между двумя вершинами.

пример графа

Задано N городов c номерами от 1 до N и сеть из M дорог с односторонним движением между ними. Каждая дорога задается тройкой (i, j, k), где i - номер города, в котором дорога начинается, j -номер города, в котором дорога заканчивается, а k - ее длина (число k - натуральное). Дороги друг с другом могут пересекаться только в концевых городах.
Все пути между двумя указанными городами A и B можно упорядочить в список по неубыванию их длин (если есть несколько путей одинаковой длины, то выбираем один из них). Необходимо найти один из путей, который может быть вторым в списке. Задание 23 (см. "Сборник задач по графам")..

Алгоритм:

1. С помощью алгоритма Дейкстры находим кратчайший (первый минимальный) путь между начальным пунктом и конечным,состоящий из дорог(рёбер) s1,..,sn.
2. Второй кратчайший путь не будет содержать хотя бы одно ребро из s_i, следовательно алгоритм нахождения второго пути будет следующим:
Для i от 1 до n
Берем ребро si из первого мин. пути и удаляем его из графа.
Находим кратчайший путь в новом графе, запоминаем его как минимальный.
Если найденный путь оказался меньше минимального, то запомним текущий путь и его длину
Восстанавливаем ребро si и делаем ту же самую процедуру для si+1

#include <iostream>
#include <fstream>
#include <iomanip>
 
using namespace std;
 
#define SIZE 100
 
 
int a[SIZE][SIZE]; // матрица смежности
const int MAX_INT = 100000; // аналог бесконечности
int d[SIZE]; // d[i] - кратчайшее расстояние(сумма весов)из заданной вершины в i-тую
int used[SIZE]; // used[i] = 1 - i-тый узел посещен иначе used[i] = 0
int prev[SIZE]; // prev[i] - номер узла, из которого мы попадаем в узел i 
int inv_path[SIZE][SIZE]; // путь
int N, M; // количество узлов , кол-во ребер
int start, end; // начальный и конечный пункт
int path_len[SIZE]; // path_len[i] - длина массива inv_path для i-го пути
 
int find_the_shortest_way(int V1, int V2, int m); // (V1, V2) - ребро, которое мы удаляем из графа, 
// m - номер мин. пути, полученного при этом
 
int main()
{
	int min_record; // второе минимальное расстояние между двумя вершинами
	int i, j; 
	int x, y, k; // xy - ребро, k - вес
 
	char *s = "input.txt"; // имя файла
 
	ifstream in(s);
 
	if(!s) cout << "Can't open file " << s << endl;
 
	in >> N >> M;
 
	for(i = 0; i < N; i++)
		for(j = 0; j < N; j++)
			a[i][j] = 0; 
 
	for(i = 0; i < M; i++)
	{
		in >> x >> y >> k;
		a[x][y] = k; // граф ориентированный
		//a[y][x] = k;  // если граф неориентированный, то убрать метку
	}
 
	// Вывод матрицы смежности для графа
	for(i=0; i< N; i++)
	{
		for(j=0; j< N ; j++)
		{
			cout << setw(8) << a[i][j];
		}
		cout << endl;
	}
 
	cout << "Enter start point : "; cin >> start; // город А
	cout << "Enter end point : "; cin >> end; // город В
 
	int path = find_the_shortest_way(0,0,0); // Первый минимальный путь(основной путь)
 
	if(path == MAX_INT) cout << "There's no way from point " << start << " to point " << end << "." << endl;
	else
	{
	   cout << "The first shortest way from "
			<< start << " to " << end << ":";
	   // Выводим путь
	   for(int i=path_len[0]-1; i>=0; i--) {cout << " " << inv_path[0][i];}
	   // Выводим его длину
	   cout << " Path length is " << path << endl;
	}
 
	int n = 1; // счетчик для индексов пути
 
	min_record = MAX_INT;
	int d;
	int min_index; // номер второго минимального пути среди всех неосновных
 
	for(j = path_len[0] - 1; j>0; j--)
	{
		d = find_the_shortest_way(inv_path[0][j], inv_path[0][j-1], n);
		if(d < min_record)
		{
			min_record = d;
			min_index = n;
		}
		n++;
	}
	if(min_record == MAX_INT) cout << "There's no way from point " << start << " to point " << end << "." << endl;
	else
	{
	   cout << "The second shortest way from "
			<< start << " to " << end << ":";
	   // Выводим путь
	   for(int i=path_len[min_index]-1; i>=0; i--) {cout << " " << inv_path[min_index][i];}
	   // Выводим его длину
	   cout << " Path length is " << min_record << endl;
	}
	return 0;
}
 
int find_the_shortest_way(int V1, int V2, int m)
{
	int i, j, w, min_v;
 
 
	for(j=0;j<N;j++)
	{
		used[j] = 0;
		d[j] = MAX_INT;
	}
 
	prev[start] = -1;
	d[start] = 0; //  кратчайший путь из start в start = 0;
	used[start] = 1; // кратчайший путь для начальной вершины найден
	w = start; // текущая вершина
 
	// Алгоритм Дейкстры 
 
	while(1)
	{
 
		for(j=0; j<N; j++)
		{
			if(a[w][j] == 0 || (w == V1 && j == V2)) continue; // вершины w и j несмежные
			if(used[j] == 0 && d[j] > d[w]+a[w][j])
			{
				d[j] = d[w] + a[w][j];
				prev[j] = w;
			}
		}
		min_v = MAX_INT;
		w = -1 ;
 
		for(j=0; j<N; j++)
		{
			if(used[j] == 0 && d[j] < min_v)
			{
				min_v = d[j];
				w = j;
			}
		}
		if(w == -1) 
		{
			return MAX_INT; 
		}
		if(w==end)
		{
			j = end; int k = 0;
			while(j!=-1)
			{
				inv_path[m][k] = j;
				j = prev[j];
				k++;
			}
			path_len[m] = k;
			return d[end];
		}
		used[w] = 1;
	}
}

ВложениеРазмер
graph_23.rar76.56 кб