Mextrom
Advanced Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
LuckyStrike
Может такой вариант подойдет?
Program.cs:
Код: using System;
namespace FordBellman
{
class Program
{
static void Main(string[] args)
{
Spisok spisok = new Spisok();
spisok.VvodVes();
spisok.Reshenie();
}
}
}
|
Spisok.cs:
Код: using System;
using System.IO;
using System.Collections.Generic;
namespace FordBellman
{
public class Spisok
{
const int MaxNodes = 7;
const int B = 1000;
private int[,] a = new int[MaxNodes, MaxNodes];
private int[] d = new int[MaxNodes];
Stack<int> stack = new Stack<int>();
public Spisok()
{
}
/// <summary>
/// Ввод матрицы весов дуг заданного графа.
/// </summary>
public void VvodVes()
{
Console.WriteLine("Вводите элементы матрицы весов дуг по строкам:");
for (int i = 0; i < MaxNodes; i++)
{
for (int j = 0; j < MaxNodes; j++)
{
Console.WriteLine("Введите A[{0}, {1}]", i + 1, j + 1);
string strValue = Console.ReadLine();
int intVal;
if (int.TryParse(strValue, out intVal))
{
a[i, j] = intVal;
if (a[i, j] == 0)
{
a[i, j] = B;
}
}
else
{
Console.WriteLine("Введено неверное значение");
return;
}
}
}
}
public void Reshenie()
{
int s; // Начальная вершина пути (источник).
int t; // Конечная вершина пути.
int u = 0;
int v;
Console.Write("Введите источник: ");
string value = Console.ReadLine();
if (!int.TryParse(value, out s))
{
Console.WriteLine("Некорректное значение");
return;
}
s--;
for (int i = 0; i < d.Length; i++)
{
d[i] = a[s, i];
}
d[s] = 0;
//Вычисление матрицы расстояний от
//источника до всех вершин графа.
for (int k = 0; k < MaxNodes - 2; k++)
{
for (int i = 0; i < MaxNodes; i++)
{
if (i != s)
{
for (int j = 0; j < MaxNodes; j++)
{
if (d[i] > d[j] + a[j, i])
{
d[i] = d[j] + a[j, i];
}
}
}
}
}
//Вывод матрицы расстояний от источника
//до всех вершин графа.
Console.WriteLine("Матрица расстояний: ");
for (int i = 0; i < d.Length; i++)
{
Console.Write(d[i] + " ");
}
Console.WriteLine();
// Нахождение кратчайшего пути из S в T с использованием
// построенной матрицы расстояний.
Console.Write("Введите конечную вершину пути: ");
value = Console.ReadLine();
if (!int.TryParse(value, out t))
{
Console.WriteLine("Некорректное значение");
return;
}
t--;
stack.Push(t);
v = t;
while (v != s)
{
for (int i = 0; i < d.Length; i++)
{
if (d[v] == d[i] + a[i, v])
{
u = i;
}
}
stack.Push(u);
v = u;
}
//Вывод кратчайшего пути на экран дисплея.
Console.Write("Кратчайший путь: ");
while (stack.Count != 0)
{
Console.Write(stack.Pop() + " ");
}
Console.WriteLine();
}
}
} |
|
Всего записей: 854 | Зарегистр. 30-03-2005 | Отправлено: 23:57 09-09-2010 | Исправлено: Mextrom, 00:00 10-09-2010 |
|
