Автор работы: Пользователь скрыл имя, 14 Декабря 2013 в 21:34, курсовая работа
Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
1. Постановка задачи 3
2. Алгоритм 3
3. Листинг 3
4. Тестирование 10
5. Вывод 13
6. Список использованных источников 13
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
"Санкт-Петербургский
Кафедра прикладной математики и математического моделирования
по дисциплине "Структуры и алгоритмы"
на тему
"Алгоритм Дейкстры"
ИСПОЛНИТЕлЬ |
||
Студент группы 1290 |
Е. С. Александрова | |
РУКОВОДИТЕЛЬ |
||
Преподаватель |
А.Я. Войткунская |
Санкт-Петербург
2012
1. Постановка задачи 3
2. Алгоритм 3
3. Листинг 3
4. Тестирование 10
5. Вывод 13
6. Список использованных источников 13
Алгоритм Дейкстры — алгоритм н
Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
3. ЛИСТИНГ
Класс Graph.cs:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Дейкстры
{
class Graph
{
public int[,] arrMatrix;
public int[,] ReadGraphWeight(int nQuantity)
{
arrMatrix = new int[nQuantity, nQuantity];
for (int i = 0; i < nQuantity; i++)
for (int j = 0; j < nQuantity; j++)
arrMatrix[i,j] = 0;
for (int i = 0; i < nQuantity; i++)
for (int j = i+1; j < nQuantity; j++)
{
Console.Write("Введите вес ребра [{0},{1}] = ",i+1,j+1);
arrMatrix[i, j] = Convert.ToInt32(Console.
}
Console.WriteLine();
return arrMatrix;
}
public int[,] PrintGraphWeight(int [,] Matrix)
{
for (int i = 0; i < Matrix.GetLength(0); i++)
Console.Write(" X{0}", i + 1);
Console.WriteLine("\n\n");
for (int i = 0; i < Matrix.GetLength(0); i++)
{
Console.Write("X{0} ", i + 1);
for (int j = 0; j < Matrix.GetLength(0); j++)
{
Console.Write("{0} ", Matrix[i,j]);
Matrix[j,i] = Matrix[i,j];
}
Console.WriteLine("\n\n");
}
for (int i = 0; i < Matrix.GetLength(0); i++)
for (int j = 0; j < Matrix.GetLength(0); j++)
if (Matrix[i,j] == 0) Matrix[i,j] = 65535;
return Matrix;
}
public int[,] AddEdge(int[,] arrMatrix)
{
Console.WriteLine("\nВведите количество ребер, которые вы хотите добавить");
int nNumber = Convert.ToInt32(Console.
for (int i = 0; i < nNumber; i++)
{
Console.WriteLine("\nВведите точку начала ребра.");
int nFirst = Convert.ToInt32(Console.
Console.WriteLine("\nВведите точку конца ребра.");
int nEnd = Convert.ToInt32(Console.
Console.WriteLine("\nВведите вес ребра.");
int nWeight = Convert.ToInt32(Console.
arrMatrix[nFirst, nEnd] = nWeight;
}
for (int i = 0; i < arrMatrix.GetLength(0); i++)
for (int j = 0; j < arrMatrix.GetLength(0); j++)
if (arrMatrix[i, j] == 65535)
arrMatrix[i, j] = 0;
Console.WriteLine();
return arrMatrix;
}
public int[,] AddPoints(int[,] arrMatrix)
{
Console.WriteLine("\nВведите количество вершин, которые вы хотите добавить.");
int nNumber = Convert.ToInt32(Console.
Console.WriteLine();
int[,] arrNewMatrix = new int[arrMatrix.GetLength(0)+
for (int i = 0; i < arrNewMatrix.GetLength(0); i++)
for (int j = i + 1; j < arrNewMatrix.GetLength(0); j++)
if ((i < arrMatrix.GetLength(0)) && (j < arrMatrix.GetLength(0)))
arrNewMatrix[i, j] = arrMatrix[i, j];
else
{
if (arrNewMatrix[i, j] == 65535)
arrNewMatrix[i, j] = 0;
Console.WriteLine("Введите [{0},{1}]", i + 1, j + 1);
arrNewMatrix[i, j] = Convert.ToInt32(Console.
if (arrNewMatrix[i, j] == 0)
arrNewMatrix[i, j] = 65535;
}
Console.WriteLine();
return arrNewMatrix;
}
public void End(int[,] arrMatrix)
{
int[,] Matrix = new int[arrMatrix.GetLength(0), arrMatrix.GetLength(0)];
Console.WriteLine("\n Введите 0, если хотите выйти из программы, \nВведите 1, если хотите добавить ребро, \nВведите 2, если хотите добавить вершину, \nВведите 3, если хотите запустить алгоритм ещё раз");
int nNumber = Convert.ToInt32(Console.
Matrix = arrMatrix;
while (nNumber != 0)
{
if (nNumber == 1)
{
Matrix=AddEdge(arrMatrix);
PrintGraphWeight(Matrix);
}
if (nNumber == 2)
{
Matrix=AddPoints(arrMatrix);
PrintGraphWeight(Matrix);
}
if (nNumber == 3)
{
Deikstri alg = new Deikstri();
alg.AlgDeikstra(Matrix);
}
if ((nNumber != 2)&&(nNumber!=1)&&(nNumber!=3)
Console.WriteLine("Ошибка");
Console.WriteLine();
Console.WriteLine("\n Введите 0, если хотите выйти из программы, \nВведите 1, если хотите добавить ребро, \nВведите 2, если хотите добавить вершину, \nВведите 3, если хотите запустить алгоритм ещё раз");
nNumber = Convert.ToInt32(Console.
Console.WriteLine();
}
}
public int nQuantitys()
{
Console.WriteLine(" Введите количество вершин:\n");
int nQuantity = Convert.ToInt32(Console.
while(nQuantity==0)
{
Console.WriteLine("\nОшибка! Введите другое количество вершин.\n");
nQuantity = Convert.ToInt32(Console.
}
Console.WriteLine();
return nQuantity;
}
}
}
Класс Deikstri.cs:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Дейкстры
{
class Deikstri:Graph
{
public int p, xn, xk;
public bool[] flag = new bool[100];
public int[] l = new int[100];
public string s;
public string[] path = new string[100];
public int min(int nQuantity)
{
int i, result = 0;
for (i = 0; i < nQuantity; i++)
if (!(flag[i])) result = i;
for (i = 0; i < nQuantity; i++)
if ((l[result] > l[i]) && (!flag[i])) result = i;
return result;
}
public int minim(int x, int y)
{
if (x < y) return x;
return y;
}
public void AlgDeikstra(int[,] Matrix)
{
Console.WriteLine("Задайте начальную точку: ");
xn = Convert.ToInt32(Console.
Console.WriteLine("Задайте конечную точку: ");
xk = Convert.ToInt32(Console.
xk--;
xn--;
if (xn == xk)
{
Console.WriteLine("Начальная и конечная точки совпадают.");
Console.ReadKey();
}
for (int i = 0; i < Matrix.GetLength(0); i++)
{
flag[i] = false;
l[i] = 65535;
}
l[xn] = 0;
flag[xn] = true;
p = xn;
s = Convert.ToString(xn + 1);
for (int i = 1; i <= Matrix.GetLength(0); i++)
{
path[i] = "X";
path[i] = path[i] + s;
}
do
{
for (int i = 0; i < Matrix.GetLength(0); i++)
if ((Matrix[p, i] != 65535) && (!flag[i]) && (i != p))
{
if (l[i] > l[p] + Matrix[p, i])
{
s = Convert.ToString(i + 1);
path[i + 1] = path[p + 1];
path[i + 1] = path[i + 1] + "-X";
path[i + 1] = path[i + 1] + s;
}
l[i] = minim(l[i], l[p] + Matrix[p, i]);
}
p = min(Matrix.GetLength(0));
flag[p] = true;
}
while (p != xk);
if (l[p] != 65535)
{
Console.WriteLine("Путь: {0}", path[p + 1]);
Console.WriteLine("Длина пути: {0}", l[p]);
}
else
Console.WriteLine("Путь не существует!");
}
}
}
Класс Program.cs:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Дейкстры
{
class Program
{
static void Main(string[] args)
{
Graph grGraf = new Graph();
Deikstri alAlgor = new Deikstri();
int nQuantity = grGraf.nQuantitys();
int[,] Matrix = new int[nQuantity, nQuantity];
Matrix = grGraf.ReadGraphWeight(
grGraf.PrintGraphWeight(
alAlgor.AlgDeikstra(Matrix);
grGraf.End(Matrix);
Console.ReadKey();
}
}
Вводим граф:
Результат:
|
5. ВЫВОД
Был разобран и изучен алгоритм Дейкстры. Была написана реализующая этот алгоритм программа. Также было проведено тестирование, которое не выявило никаких проблем. Программы работает без сбоев и ошибок.
6. СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Роберт Седжвик. Фундаментальные алгоритмы
на C++. Часть 5 2. http://ru.wikipedia.org/wiki/А
|