Автор работы: Пользователь скрыл имя, 23 Декабря 2013 в 20:17, контрольная работа
Алгори́тм Де́йкстры (Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.
1.ОПИСАНИЕ АЛГОРИТМА………………………………………………………………….3
2.КОД……………………………………………………………………………………………..4
3.РЕЗУЛЬТАТЫ РАБОТЫ…………………
СОДЕРЖАНИЕ
1.ОПИСАНИЕ АЛГОРИТМА…………………………
2.КОД…………………………………………………………………
3.РЕЗУЛЬТАТЫ РАБОТЫ……………………………………………………….……
1. ОПИСАНИЕ АЛГОРИТМА
Алгори́тм Де́йкстры (Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.
Дан взвешенный неориентированный граф без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины графа до всех остальных вершин этого графа.
Логика алгоритма
Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда нельзя больше обработать ни одной вершины.
2. КОД
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace alDeikstry
{
class Graf
{
int N; // количество вершин
bool[,] adj_matrix;// матрица смежности
int[,] cost; // веса рёбер
int[] dist ; // расстояния от заданной вершины
int[] parent;// из какой вершины пришли
public Graf()
{
N = 100;
adj_matrix = new bool[N, N];
cost = new int[N, N];
dist = new int[N];
parent = new int[N];
}
public void dijkstra(int start)
{
// in_tree[i] == true, если для вершины i уже посчитано минимальное расстояние
bool[] in_tree =new bool[N];
dist = new int[N];
parent = new int[N];
for (int i = 0; i < N; i++)
parent[i] = 15555;
for (int i = 0; i < N; i++)
dist[i] = Int32.MaxValue;
dist[start] = 0;
int cur = start;
while(!in_tree[cur])
{
in_tree[cur] = true;
for(int i = 0; i < N; i++)
{
if(adj_matrix[cur,i])
{
int d = dist[cur] + cost[cur,i];
if(d < dist[i])
{
dist[i] = d;
parent[i] = cur;
}
}
}
int min_dist = Int32.MaxValue;
for(int i = 0; i < N; i++)
{
if(!in_tree[i] && (dist[i] < min_dist))
{
cur = i;
min_dist = dist[i];
}
}
}
}
public void Read()
{
Console.WriteLine("Введите количество вершин");
N = Convert.ToInt32(Console.
adj_matrix = new bool[N, N];
bool sm = false;
Console.WriteLine("Введите 1 если ребро есть, 0 если его нет: ");
for (int i = 0; i < N; i++)
for (int j = 0; (i>j)&&(j < N); j++)
{
Console.WriteLine("между вершинами {0} и {1}", i + 1, j + 1);
sm = (Convert.ToInt32(Console.
adj_matrix[i, j] = sm;
adj_matrix[j, i] = sm;
}
Console.WriteLine("Введите вес ребра: ");
cost = new int[N, N];
int ch = Int32.MaxValue;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cost[i, j] = ch;
for (int i = 0; i < N; i++)
for (int j = 0; (i>j)&&(j < N); j++)
if (adj_matrix[i, j] == true)
{
Console.WriteLine("между вершинами {0} и {1}", i + 1, j + 1);
ch = Convert.ToInt32(Console.
cost[i, j] = ch;
cost[j, i] = ch;
}
}
public void Write()
{
Console.WriteLine("матрица имеет вид:");
for (int i = 0; i < N; i++)
{
Console.Write("\n");
for (int j = 0; j < N; j++)
Console.Write("{0,5} ", (adj_matrix [i, j] == true?1:0));
Console.WriteLine();
}
Console.WriteLine("вес :");
for (int i = 0; i < N; i++)
{
Console.Write("\n");
for (int j = 0; j < N; j++)
Console.Write("{0,5} ", (cost[i,j]==int.MaxValue)?0:
Console.WriteLine();
}
}
public void WritePut(int Start)
{
Console.WriteLine("кратчайший путь от {0} :", Start +1);
for (int i = 0; i < dist.Length; i++)
Console.WriteLine("до {0} равен {1}", i+1, dist[i]);
}
}
class Program
{
static void Main(string[] args)
{
Graf m_Graf = new Graf();
m_Graf.Read();
m_Graf.Write();
Console.WriteLine("введите стартовую вершину");
int Start = Convert.ToInt32(Console.
m_Graf.dijkstra(Start);
m_Graf.WritePut(Start);
Console.ReadKey();
}
}
}
3. РЕЗУЛЬТАТЫ РАБОТЫ