Задача о размещениях

src, tmpr.dest] = tmpr.weight;
if (!_IsOrient)
tmp[tmpr.dest, tmpr.src] = tmpr.weight;
}
return tmp;
}
/// <summary>
/// Получение медианы
/// </summary>
/// <returns>Метка медианы</returns>
public String GetMedian()
{
float[,] DN = GetDN();
float min,tmp;
int ind;

ind = -1;
min = 0;
for (int i = 0; i < _VertexCount; i++)
{
tmp = 0;
for (int j = 0; j < _VertexCount; j++)
{
if (DN[i, j] < 0)
{
tmp = DN[i, j];
break;
}
else
{
tmp += DN[i, j];
}
}
if (tmp > 0)
{
if (min > tmp)
{
min = tmp;
ind = i;
}
else
{
if (min <= 0)
{
min = tmp;
ind = i;
};
}
}
}
if (ind > -1)
{
return _VertexLabels[ind];
}
return null;
}
/// <summary>
/// Получение матрицы кратчайших расстояний
/// </summary>
/// <returns>Двумерный массив кратчайших расстояний</returns>
public float[,] GetDN()
{
float[,] DN_1 = GetD0();
int cnt = 1;
float[,] DN = new float[_VertexCount, _VertexCount];

/// Пока количество итераций меньше количества вершин
while (cnt < _VertexCount)
{
for (int i=0; i < _VertexCount; i++)
for (int j = 0; j < _VertexCount; j++)

{
/// Для каждой пары вершин
/// Получаем текущее кратчайшее расстояние
float min = DN_1 [i, j];
/// Lkz всех третьих вершин проверяем
for (int k = 0; k < _VertexCount; k++)
{

// Не явлеятся путь через неё короче
if ( DN_1[i,k] >= 0)
if (DN_1[k, j] >= 0)
{
if (min >= 0)
{
min = DN_1[i, k] + DN_1[k, j] > min ? min : DN_1[i, k] + DN_1[k, j];
}
else
{
min = DN_1[i, k] + DN_1[k, j];
}
}
}
DN[i,j] = min;
}
DN_1 = DN;
cnt++;
}
return DN;
}
/// <summary>
/// Свойство количество вершин - тьолько для чтения
/// </summary>
public int VertexCount
{
get {
return _VertexCount;
}
}
}
}
Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;
namespace Medians
{
static class Program
{
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main()
{
Application.EnableVisualStyles();
Application.SetCompatibleTextRenderingDefault(false);
Application.Run(new frmMain());
}
}
}
Тестирующие примеры
Пример № 1
Исходные данные
(Ребро – Ребро: Вес)
1-2:4
1-3:5
1-6:2
Результаты работы программы
Матрица весов
0 4 5 2
∞ 0 ∞ ∞
∞ ∞ 0 ∞
∞ ∞ ∞ 0
Матрица длин кратчайших путей
0 4 5 2
∞ 0 ∞ ∞
∞ ∞ 0 ∞
∞ ∞ ∞ 0
Медиана - 1
Пример № 2
Исходные данные
(Ребро – Ребро: Вес)
1-2:4
1-3:5
1-6:2
6-1:0,5
Результаты работы программы
Матрица весов
0 4 5 2
∞ 0 ∞ ∞
∞ ∞ 0 ∞
0,5 ∞ ∞ 0
Матрица длин кратчайших путей
0 4 5 2
∞ 0 ∞ ∞
∞ ∞ 0 ∞
0,5 4,5 5,5 0
Медиана – 6
Пример № 3
Исходные данные
(Ребро – Ребро: Вес)
1-2:4
1-3:5
1-6:2
6-1:0,5
7-8:9
Результаты работы программы
Матрица весов
0 4 5 2 ∞ ∞
∞ 0 ∞ ∞ ∞ ∞
∞ ∞ 0 ∞ ∞ ∞
0,5 ∞ ∞ 0 ∞ ∞
∞ ∞ ∞ ∞ 0 9
∞ ∞ ∞ ∞ ∞ 0
Матрица длин кратчайших путей
0 4 5 2 ∞ ∞
∞ 0 ∞ ∞ ∞ ∞
∞ ∞ 0 ∞ ∞ ∞
0,5 4,5 5,5 0 ∞ ∞
∞ ∞ ∞ ∞ 0 9
∞ ∞ ∞ ∞ ∞ 0
Медианы нет