Исправить реализацию алгоритма Дейкстры - C#
Формулировка задачи:
Подскажите пожалуйста новичку, как подставлять начальную и конечную точку графа, а точнее сделать их переменными , кто подскажет буду очень благодарен!
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
class DekstraAlgorim
{
public Point[] points { get; private set; }
public Rebro[] rebra { get; private set; }
public Point BeginPoint { get; private set; }
public DekstraAlgorim(Point[] pointsOfgrath, Rebro[] rebraOfgrath)
{
points = pointsOfgrath;
rebra = rebraOfgrath;
}
/// <summary>
/// Запуск алгоритма расчета
/// </summary>
/// <param name="beginp"></param>
public void AlgoritmRun(Point beginp)
{
if (this.points.Count() == 0 || this.rebra.Count() == 0)
{
throw new DekstraException("Массив вершин или ребер не задан!");
}
else
{
BeginPoint = beginp;
OneStep(beginp);
foreach (Point point in points)
{
Point anotherP = GetAnotherUncheckedPoint();
if (anotherP != null)
{
OneStep(anotherP);
}
else
{
break;
}
}
}
}
/// <summary>
/// Метод, делающий один шаг алгоритма. Принимает на вход вершину
/// </summary>
/// <param name="beginpoint"></param>
public void OneStep(Point beginpoint)
{
foreach (Point nextp in Pred(beginpoint))
{
if (nextp.IsChecked == false)//не отмечена
{
float newmetka = beginpoint.ValueMetka + GetMyRebro(nextp, beginpoint).Weight;
if (nextp.ValueMetka > newmetka)
{
nextp.ValueMetka = newmetka;
nextp.predPoint = beginpoint;
}
else
{
}
}
}
beginpoint.IsChecked = true;//вычеркиваем
}
/// <summary>
/// Поиск соседей для вершины. Для неориентированного графа ищутся все соседи.
/// </summary>
/// <param name="currpoint"></param>
/// <returns></returns>
private IEnumerable<Point> Pred(Point currpoint)
{
IEnumerable<Point> firstpoints = from ff in rebra where ff.FirstPoint == currpoint select ff.SecondPoint;
IEnumerable<Point> secondpoints = from sp in rebra where sp.SecondPoint == currpoint select sp.FirstPoint;
IEnumerable<Point> totalpoints = firstpoints.Concat<Point>(secondpoints);
return totalpoints;
}
/// <summary>
/// Получаем ребро, соединяющее 2 входные точки
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
private Rebro GetMyRebro(Point a, Point b)
{//ищем ребро по 2 точкам
IEnumerable<Rebro> myr = from reb in rebra where (reb.FirstPoint == a & reb.SecondPoint == b) || (reb.SecondPoint == a & reb.FirstPoint == b) select reb;
if (myr.Count() > 1 || myr.Count() == 0)
{
throw new DekstraException("Не найдено ребро между соседями!");
}
else
{
return myr.First();
}
}
/// <summary>
/// Получаем очередную неотмеченную вершину, "ближайшую" к заданной.
/// </summary>
/// <returns></returns>
private Point GetAnotherUncheckedPoint()
{
IEnumerable<Point> pointsuncheck = from p in points where p.IsChecked == false select p;
if (pointsuncheck.Count() != 0)
{
float minVal = pointsuncheck.First().ValueMetka;
Point minPoint = pointsuncheck.First();
foreach (Point p in pointsuncheck)
{
if (p.ValueMetka < minVal)
{
minVal = p.ValueMetka;
minPoint = p;
}
}
return minPoint;
}
else
{
return null;
}
}
public List<Point> MinPath1(Point end)
{
List<Point> listOfpoints = new List<Point>();
Point tempp = new Point();
tempp = end;
while (tempp != this.BeginPoint)
{
listOfpoints.Add(tempp);
tempp = tempp.predPoint;
}
return listOfpoints;
}
}
/// <summary>
/// Класс, реализующий ребро
/// </summary>
class Rebro
{
public Point FirstPoint { get; private set; }
public Point SecondPoint { get; private set; }
public float Weight { get; private set; }
public Rebro(Point first, Point second, float valueOfWeight)
{
FirstPoint = first;
SecondPoint = second;
Weight = valueOfWeight;
}
}
/// <summary>
/// Класс, реализующий вершину графа
/// </summary>
class Point
{
public float ValueMetka { get; set; }
public string Name { get; private set; }
public bool IsChecked { get; set; }
public Point predPoint { get; set; }
public object SomeObj { get; set; }
public Point(int value, bool ischecked)
{
ValueMetka = value;
IsChecked = ischecked;
predPoint = new Point();
}
public Point(int value, bool ischecked, string name)
{
ValueMetka = value;
IsChecked = ischecked;
Name = name;
predPoint = new Point();
}
public Point()
{
}
}
// <summary>
/// для печати графа
/// </summary>
static class PrintGrath
{
public static List<string> PrintAllPoints(DekstraAlgorim da)
{
List<string> retListOfPoints = new List<string>();
foreach (Point p in da.points)
{
retListOfPoints.Add(string.Format("point name={0}, point value={1}, predok={2}", p.Name, p.ValueMetka, p.predPoint.Name ?? "нет предка"));
}
return retListOfPoints;
}
public static List<string> PrintAllMinPaths(DekstraAlgorim da)
{
List<string> retListOfPointsAndPaths = new List<string>();
foreach (Point p in da.points)
{
if (p != da.BeginPoint)
{
string s = string.Empty;
foreach (Point p1 in da.MinPath1(p))
{
s += string.Format("{0} ", p1.Name);
}
retListOfPointsAndPaths.Add(string.Format("Point ={0},MinPath from {1} = {2}", p.Name, da.BeginPoint.Name, s));
}
}
return retListOfPointsAndPaths;
}
}
class DekstraException : ApplicationException
{
public DekstraException(string message)
: base(message)
{
}
}
class Program
{
static void Main(string[] args)
{
Point[] v = new Point[6];
v[0] = new Point(99999, false, "Chs");
v[1] = new Point(99999, false, "Kv");
v[2] = new Point(99999, false, "Chg");
v[3] = new Point(99999, false, "Zht");
v[4] = new Point(99999, false, "Pl");
v[5] = new Point(99999, false, "Vn");
Rebro[] rebras = new Rebro[9];
rebras[0] = new Rebro(v[0], v[1], 190);//Chs-Kv
rebras[1] = new Rebro(v[0], v[5], 343);//Chs-Vn
rebras[2] = new Rebro(v[0], v[4], 279);//Chs-Pl
rebras[3] = new Rebro(v[5], v[1], 256);//Vn-Kv
rebras[4] = new Rebro(v[5], v[3], 125);//Vn-Zht
rebras[5] = new Rebro(v[3], v[1], 131);//Zht-Kv
rebras[6] = new Rebro(v[1], v[2], 149);//Kv-Chg
rebras[7] = new Rebro(v[1], v[4], 337);//Kv-Pl
rebras[8] = new Rebro(v[2], v[4], 477);//CHG-Pl
DekstraAlgorim da = new DekstraAlgorim(v, rebras);
da.AlgoritmRun(v[0]);
List<string> b = PrintGrath.PrintAllMinPaths(da);
for (int i = 0; i < b.Count; i++)
Console.WriteLine(b[i]);
Console.ReadKey(true);
}
}
}Решение задачи: «Исправить реализацию алгоритма Дейкстры»
textual
Листинг программы
using System;
using System.Collections.Generic;
namespace Dijkstra
{
class Program
{
private static void Main()
{
const int n = 5;
var adjacencyMatrix = new int[n, n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
adjacencyMatrix[i, j] = -1;
}
}
adjacencyMatrix[0, 1] = 10;
adjacencyMatrix[0, 3] = 30;
adjacencyMatrix[0, 4] = 100;
adjacencyMatrix[1, 2] = 50;
adjacencyMatrix[2, 0] = 70;
adjacencyMatrix[2, 4] = 10;
adjacencyMatrix[3, 2] = 20;
adjacencyMatrix[4, 3] = 60;
var costs = new int[n];
for (int i = 1; i < costs.Length; i++)
{
costs[i] = int.MaxValue;
}
for (int i = 0; i < n; i++)
{
var list = new List<int>();
for (int j = i; j < n; j++)
{
if (adjacencyMatrix[i, j] != -1)
list.Add(j);
}
list.Sort((x, y) => adjacencyMatrix[i, x].CompareTo(adjacencyMatrix[i, y])); //Сортируем по мин. стоимости пути
foreach (var j in list)
{
var newcost = costs[i] + adjacencyMatrix[i, j];
if (newcost < costs[j])
costs[j] = newcost;
}
}
for (int i = 0; i < costs.Length; i++)
{
Console.WriteLine("Пункт {0}, стоимость пути = {1}", i, costs[i]);
}
Console.ReadKey();
}
}
}