Задача 116: Вагонетка

FindMyWay.cs

using System;
using System.Linq;
using System.Collections.Generic;
					
public class Program
{
	class RoadBetweenCity
	{
		public int FirstCity;
		public int SecondCity;
	}
	
	static double[,] GetGraph(int K, double[] cost, RoadBetweenCity[] roads)
	{
		// начальная инициализация вершин графа макс.значениями
		double[,] graph = new double[K, K];
		for (int i = 0; i < K; i++)
		{
			for (int j = 0; j < K; j++)
			{	
				graph[i, j] = double.MaxValue;
			}
		}
			
		// создаем граф: вершины графа - это номера поселков, 
		// ребра - стоимость проезда между двумя поселками, 
		// а именно стоимость канистры горючего в поселке отправления
		for (int i = 0; i < roads.Length; i++)
		{
			int firstCity = roads[i].FirstCity - 1;
			int secondCity = roads[i].SecondCity - 1;
			graph[firstCity, secondCity] = cost[firstCity];
			graph[secondCity, firstCity] = cost[secondCity];
		}
		
		return graph;
	}
	
	static void ShowWay(int K, int[] path, double[] dist)
	{
		// Восстановление пути с помощью массива path
		Stack<int> stack = new Stack<int>();
		for (int v = K - 1; v != -1; v = path[v])
		{
			stack.Push(v);
		}
		
		int[] res = new int[stack.Count];
		for (int i = 0; i < res.Length; i++)
		{
			res[i] = stack.Pop() + 1;
		}
		
		// Если значение для K равно начальному значению (MaxValue),
		// то пути до требуемой вершины не существует.
		if (dist[K - 1] == double.MaxValue)
		{
			Console.WriteLine("No way!");
		}
		else
		{
			// минимальная стоимость маршрута между 1-м и K-м поселком
			// (суммарная стоимость канистр горючего)
			Console.WriteLine("{0}", dist[K - 1]);
			
			// кратчайший путь
			Console.WriteLine("{0}\n", string.Join(" -> ", res));
		}
	}
	
	static void DijkstraAlgorithm(double[] cost, RoadBetweenCity[] roads)
	{
		int K = cost.Length; // кол-во поселкой
		double[,] graph = GetGraph(K, cost, roads);
		
		bool[] used = new bool[K]; // массив пометок
		int[] path = Enumerable.Repeat(-1, K).ToArray(); // массив предков
		double[] dist = Enumerable.Repeat(double.MaxValue, K).ToArray(); // массив расстояний
		dist[0] = 0;
		
		// Алгоритм Дейкстры: 
		// на каждой итерации находим вершину w с минимальным расстоянием Min до истока. 
		// Если получим w = -1, то искомого пути не существует и завершаем цикл
		for (int v = 0; v < K; v++)
		{
			double Min = double.MaxValue;
			int w = -1;
			for (int j = 0; j < K; j++)
			{
				if (!used[j] && dist[j] < Min)
				{
					Min = dist[j];
					w = j;
				}
			}
			
			if (w < 0) break; // завершаем цикл
			
			// проверяем смежные вершины графа
			for (int j = 0; j < K; j++)
			{
				// если можем улучшить оценку расстояния
				if (!used[j] && dist[w] + graph[w, j] < dist[j])
				{
					dist[j] = dist[w] + graph[w, j]; // то улучшаем ее
					path[j] = w; // помечаем предка
				}
			}
			
			used[w] = true; // помечаем пройденную вершину
		}
		
		// Восстановление пути и его вывод
		ShowWay(K, path, dist);
	}	
	
	public static void Main()
	{
		Console.WriteLine("UniLecs");
		
		double[] cost_1 = new double[] { 2, 7, 4, 12 };
		RoadBetweenCity[] roads_1 = new RoadBetweenCity[]
		{
			new RoadBetweenCity { FirstCity = 1, SecondCity = 2 },
			new RoadBetweenCity { FirstCity = 1, SecondCity = 3 },
			new RoadBetweenCity { FirstCity = 4, SecondCity = 2 },
			new RoadBetweenCity { FirstCity = 4, SecondCity = 3 }
		};
		DijkstraAlgorithm(cost_1, roads_1); // Total Cost: 6; Path: 1 -> 3 -> 4
		
		double[] cost_2 = new double[] { 5, 10, 1 };
		RoadBetweenCity[] roads_2 = new RoadBetweenCity[]
		{
			new RoadBetweenCity { FirstCity = 1, SecondCity = 3 },
			new RoadBetweenCity { FirstCity = 1, SecondCity = 2 },
			new RoadBetweenCity { FirstCity = 2, SecondCity = 3 }
		};
		DijkstraAlgorithm(cost_2, roads_2); // Total Cost: 5; Path 1 -> 3
	}
}