CSharp · Console
using System;
using System.Collections.Generic;
using System.Linq;
public class Program
{
class SafeWay
{
public double SafeValue { get; set; }
public List<int> Crossroads { get; set; }
}
static SafeWay GetSafeWay(int N, Dictionary<Tuple<int, int>, double> roadOfDeathDict)
{
// массив, где храним посещенные/непосещенные перекрестки
var safeRoads = new int[N + 1];
// i-й элемент массива хранит макс.вероятность спастись
// на пути из 1го перекрестка до i-го.
var safeValues = new double[N + 1];
// т.к. дорогу можно считать двусторонней, то
// (i, j, value) = (j, i, value)
var keys = roadOfDeathDict.Keys.ToArray();
foreach (Tuple<int, int> key in keys)
{
double safeValue = roadOfDeathDict[key] / 100.0; // работаем в абсолютных значениях
roadOfDeathDict[key] = safeValue;
roadOfDeathDict.Add(new Tuple<int, int>(key.Item2, key.Item1), safeValue);
}
var safeWay = new List<int>();
safeValues[1] = 1; // на 1-м перекрестке вероятность спастись 100% (мышь пока не начала путь)
int k = 0;
// Алгоритм Дейкстры
for (int i = 1; i < N; i++)
{
// На очередной итерации выбирается перекресток k
// с наибольшей величиной safeValues[j] среди ещё не помеченных
double max = 0;
for (int j = 1; j <= N; j++)
{
if (safeRoads[j] != 1 && safeValues[j] > max)
{
max = safeValues[j];
k = j;
}
}
// далее просматриваем все перекрестки исходящие из выбранного k
// и для каждого такого перекрестка пытаемся улучшить вероятность спастись (берем макс.вероятность)
for (int j = 1; j <= N; j++)
{
if (safeRoads[j] != 1)
{
double safeValue;
roadOfDeathDict.TryGetValue(new Tuple<int, int>(k, j), out safeValue);
safeValues[j] = Math.Max(safeValues[j], (safeValues[k] * safeValue));
}
}
// помечем перекресток k как пройденный
// и сохраняем в наш маршрут
safeRoads[k] = 1;
safeWay.Add(k);
}
return new SafeWay
{
SafeValue = safeValues[N] * 100, // convert to %
Crossroads = safeWay
};
}
public static void Main()
{
Console.WriteLine("UniLecs");
// для удобства используем обьект Dictionary, но тут можно было использовать обычный двухмерный массив!
Dictionary<Tuple<int, int>, double> roadOfDeathDict = new Dictionary<Tuple<int, int>, double>()
{
{ new Tuple<int, int>(1, 2), 52 },
{ new Tuple<int, int>(1, 3), 71.5 },
{ new Tuple<int, int>(1, 4), 83.8 },
{ new Tuple<int, int>(2, 3), 71 },
{ new Tuple<int, int>(3, 4), 93 },
{ new Tuple<int, int>(3, 5), 82 },
{ new Tuple<int, int>(2, 5), 99.9 }
};
SafeWay result = GetSafeWay(5, roadOfDeathDict);
// 1 -> 4 -> 3 -> 5
// ~ 63.9
Console.WriteLine(string.Format(
"Safe way: {0}; \nSafe value of this way: {1} %",
string.Join(" -> ", result.Crossroads),
result.SafeValue ));
}
}