Алгоритмы | www.nookery.ru

Рубрика: Алгоритмы

Реализация алгоритмов на C#

Реализация алгоритма Dijkstra для определения кратчайшего пути на C#

В этой статье мы изучим на c# реализацию алгоритма Dijkstra для определения кратчайшего пути Алгоритм Дейкстры-это алгоритм нахождения кратчайших путей между узлами в графах . Он был разработан компьютерным ученым Edsger W. Dijkstra в 1956 году.Этот алгоритм помогает найти кратчайший путь от точки на графике (источника) до места назначения.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace DijkstraAlgorithm
{
    class Dijkstra
    {

        private static int MinimumDistance(int[] distance, bool[] shortestPathTreeSet, int verticesCount)
        {
            int min = int.MaxValue;
            int minIndex = 0;

            for (int v = 0; v < verticesCount; ++v)
            {
                if (shortestPathTreeSet[v] == false && distance[v] <= min)
                {
                    min = distance[v];
                    minIndex = v;
                }
            }

            return minIndex;
        }

        private static void Print(int[] distance, int verticesCount)
        {
            Console.WriteLine("Вершина    Расстояние от источника");

            for (int i = 0; i < verticesCount; ++i)
                Console.WriteLine("{0}\t  {1}", i, distance[i]);
        }

        public static void DijkstraAlgo(int[,] graph, int source, int verticesCount)
        {
            int[] distance = new int[verticesCount];
            bool[] shortestPathTreeSet = new bool[verticesCount];

            for (int i = 0; i < verticesCount; ++i)
            {
                distance[i] = int.MaxValue;
                shortestPathTreeSet[i] = false;
            }

            distance[source] = 0;

            for (int count = 0; count < verticesCount - 1; ++count)
            {
                int u = MinimumDistance(distance, shortestPathTreeSet, verticesCount);
                shortestPathTreeSet[u] = true;

                for (int v = 0; v < verticesCount; ++v)
                    if (!shortestPathTreeSet[v] && Convert.ToBoolean(graph[u, v]) && distance[u] != int.MaxValue && distance[u] + graph[u, v] < distance[v])
                        distance[v] = distance[u] + graph[u, v];
            }

            Print(distance, verticesCount);
        }

        static void Main(string[] args)
        {
            int[,] graph =  {
                         { 0, 6, 0, 0, 0, 0, 0, 9, 0 },
                         { 6, 0, 9, 0, 0, 0, 0, 11, 0 },
                         { 0, 9, 0, 5, 0, 6, 0, 0, 2 },
                         { 0, 0, 5, 0, 9, 16, 0, 0, 0 },
                         { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
                         { 0, 0, 6, 0, 10, 0, 2, 0, 0 },
                         { 0, 0, 0, 16, 0, 2, 0, 1, 6 },
                         { 9, 11, 0, 0, 0, 0, 1, 0, 5 },
                         { 0, 0, 2, 0, 0, 0, 6, 5, 0 }
                            };

            DijkstraAlgo(graph, 0, 9);
            Console.ReadKey();
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Diagnostics;

namespace DijkstraAlgorithm

{

class Dijkstra

{

private static int MinimumDistance(int[] distance, bool[] shortestPathTreeSet, int verticesCount)

{

int min = int.MaxValue;

int minIndex = 0;

for (int v = 0; v < verticesCount; ++v)

{

if (shortestPathTreeSet[v] == false && distance[v] <= min)

{

min = distance[v];

minIndex = v;

}

return minIndex;

}

private static void Print(int[] distance, int verticesCount)

{

Console.WriteLine("Вершина Расстояние от источника");

for (int i = 0; i < verticesCount; ++i)

Console.WriteLine("{0}\t {1}", i, distance[i]);

}

public static void DijkstraAlgo(int[,] graph, int source, int verticesCount)

{

int[] distance = new int[verticesCount];

bool[] shortestPathTreeSet = new bool[verticesCount];

for (int i = 0; i < verticesCount; ++i)

{

distance[i] = int.MaxValue;

shortestPathTreeSet[i] = false;

}

distance[source] = 0;

for (int count = 0; count < verticesCount - 1; ++count)

{

int u = MinimumDistance(distance, shortestPathTreeSet, verticesCount);

shortestPathTreeSet[u] = true;

for (int v = 0; v < verticesCount; ++v)

if (!shortestPathTreeSet[v] && Convert.ToBoolean(graph[u, v]) && distance[u] != int.MaxValue && distance[u] + graph[u, v] < distance[v])

distance[v] = distance[u] + graph[u, v];

}

Print(distance, verticesCount);

}

static void Main(string[] args)

{

int[,] graph = {

{ 0, 6, 0, 0, 0, 0, 0, 9, 0 },

{ 6, 0, 9, 0, 0, 0, 0, 11, 0 },

{ 0, 9, 0, 5, 0, 6, 0, 0, 2 },

{ 0, 0, 5, 0, 9, 16, 0, 0, 0 },

{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },

{ 0, 0, 6, 0, 10, 0, 2, 0, 0 },

{ 0, 0, 0, 16, 0, 2, 0, 1, 6 },

{ 9, 11, 0, 0, 0, 0, 1, 0, 5 },

{ 0, 0, 2, 0, 0, 0, 6, 5, 0 }

};

DijkstraAlgo(graph, 0, 9);

Console.ReadKey();

}

Вывод: Вершина Расстояние от […]

Реализация алгоритма Floyd-Warshall на C#

В этой статье мы изучим на c# реализацию алгоритма Флойда-Уоршолла для определения кратчайших путей во взвешенном графе с положительными или отрицательными весами ребер.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace FloydWarshallAlgorithm
{
    class FloydWarshallAlgo
    {

        public const int cst = 9999;

        private static void Print(int[,] distance, int verticesCount)
        {
            Console.WriteLine("Кратчайшее расстояния между каждой парой вершин:");

            for (int i = 0; i < verticesCount; ++i)
            {
                for (int j = 0; j < verticesCount; ++j)
                {
                    if (distance[i, j] == cst)
                        Console.Write("cst".PadLeft(7));
                    else
                        Console.Write(distance[i, j].ToString().PadLeft(7));
                }

                Console.WriteLine();
            }
        }

        public static void FloydWarshall(int[,] graph, int verticesCount)
        {
            int[,] distance = new int[verticesCount, verticesCount];

            for (int i = 0; i < verticesCount; ++i)
                for (int j = 0; j < verticesCount; ++j)
                    distance[i, j] = graph[i, j];

            for (int k = 0; k < verticesCount; ++k)
            {
                for (int i = 0; i < verticesCount; ++i)
                {
                    for (int j = 0; j < verticesCount; ++j)
                    {
                        if (distance[i, k] + distance[k, j] < distance[i, j])
                            distance[i, j] = distance[i, k] + distance[k, j];
                    }
                }
            }

            Print(distance, verticesCount);
        }
        static void Main(string[] args)
        {
            int[,] graph = {
                         { 0,   6,  cst, 11 },
                         { cst, 0,   4, cst },
                         { cst, cst, 0,   2 },
                         { cst, cst, cst, 0 }
                           };

            FloydWarshall(graph, 4);
            Console.ReadKey();

        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Diagnostics;

namespace FloydWarshallAlgorithm

{

class FloydWarshallAlgo

{

public const int cst = 9999;

private static void Print(int[,] distance, int verticesCount)

{

Console.WriteLine("Кратчайшее расстояния между каждой парой вершин:");

for (int i = 0; i < verticesCount; ++i)

{

for (int j = 0; j < verticesCount; ++j)

{

if (distance[i, j] == cst)

Console.Write("cst".PadLeft(7));

else

Console.Write(distance[i, j].ToString().PadLeft(7));

}

Console.WriteLine();

}

public static void FloydWarshall(int[,] graph, int verticesCount)

{

int[,] distance = new int[verticesCount, verticesCount];

for (int i = 0; i < verticesCount; ++i)

for (int j = 0; j < verticesCount; ++j)

distance[i, j] = graph[i, j];

for (int k = 0; k < verticesCount; ++k)

{

for (int i = 0; i < verticesCount; ++i)

{

for (int j = 0; j < verticesCount; ++j)

{

if (distance[i, k] + distance[k, j] < distance[i, j])

distance[i, j] = distance[i, k] + distance[k, j];

}

Print(distance, verticesCount);

}

static void Main(string[] args)

{

int[,] graph = {

{ 0, 6, cst, 11 },

{ cst, 0, 4, cst },

{ cst, cst, 0, 2 },

{ cst, cst, cst, 0 }

};

FloydWarshall(graph, 4);

Console.ReadKey();

}

Вывод: Кратчайшее расстояние между каждой парой вершин:0 6 10 11cst 0 4 6cst cst 0 2cst cst cst 0

Реализация алгоритма Bellman-Ford на C#

В этом примере мы изучим реализацию на языке C# алгоритма Беллмана–Форда для определения кратчайших путей от одной исходной вершины до всех остальных вершин в взвешенном графе

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace BellmanFordAlgorithm
{
    class BellmanFordAlgo
    {
        public struct Edge
        {
            public int Source;
            public int Destination;
            public int Weight;
        }

        public struct Graph
        {
            public int VerticesCount;
            public int EdgesCount;
            public Edge[] edge;
        }

        public static Graph CreateGraph(int verticesCount, int edgesCount)
        {
            Graph graph = new Graph();
            graph.VerticesCount = verticesCount;
            graph.EdgesCount = edgesCount;
            graph.edge = new Edge[graph.EdgesCount];

            return graph;
        }

        private static void Print(int[] distance, int count)
        {
            Console.WriteLine("Расстояние до вершины от источника");

            for (int i = 0; i < count; ++i)
                Console.WriteLine("{0}\t {1}", i, distance[i]);
        }

        public static void BellmanFord(Graph graph, int source)
        {
            int verticesCount = graph.VerticesCount;
            int edgesCount = graph.EdgesCount;
            int[] distance = new int[verticesCount];

            for (int i = 0; i < verticesCount; i++)
                distance[i] = int.MaxValue;

            distance[source] = 0;

            for (int i = 1; i <= verticesCount - 1; ++i)
            {
                for (int j = 0; j < edgesCount; ++j)
                {
                    int u = graph.edge[j].Source;
                    int v = graph.edge[j].Destination;
                    int weight = graph.edge[j].Weight;

                    if (distance[u] != int.MaxValue && distance[u] + weight < distance[v])
                        distance[v] = distance[u] + weight;
                }
            }

            for (int i = 0; i < edgesCount; ++i)
            {
                int u = graph.edge[i].Source;
                int v = graph.edge[i].Destination;
                int weight = graph.edge[i].Weight;

                if (distance[u] != int.MaxValue && distance[u] + weight < distance[v])
                    Console.WriteLine("Граф содержит цикл отрицательного веса.");
            }

            Print(distance, verticesCount);
        }

        static void Main(string[] args)
        {
            int verticesCount = 5;
            int edgesCount = 8;
            Graph graph = CreateGraph(verticesCount, edgesCount);

            // Edge 0-1
            graph.edge[0].Source = 0;
            graph.edge[0].Destination = 1;
            graph.edge[0].Weight = -1;

            // Edge 0-2
            graph.edge[1].Source = 0;
            graph.edge[1].Destination = 2;
            graph.edge[1].Weight = 4;

            // Edge 1-2
            graph.edge[2].Source = 1;
            graph.edge[2].Destination = 2;
            graph.edge[2].Weight = 3;

            // Edge 1-3
            graph.edge[3].Source = 1;
            graph.edge[3].Destination = 3;
            graph.edge[3].Weight = 2;

            // Edge 1-4
            graph.edge[4].Source = 1;
            graph.edge[4].Destination = 4;
            graph.edge[4].Weight = 2;

            // Edge 3-2
            graph.edge[5].Source = 3;
            graph.edge[5].Destination = 2;
            graph.edge[5].Weight = 5;

            // Edge 3-1
            graph.edge[6].Source = 3;
            graph.edge[6].Destination = 1;
            graph.edge[6].Weight = 1;

            // Edge 4-3
            graph.edge[7].Source = 4;
            graph.edge[7].Destination = 3;
            graph.edge[7].Weight = -3;

            BellmanFord(graph, 0);
            Console.ReadKey();
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Diagnostics;

namespace BellmanFordAlgorithm

{

class BellmanFordAlgo

{

public struct Edge

{

public int Source;

public int Destination;

public int Weight;

}

public struct Graph

{

public int VerticesCount;

public int EdgesCount;

public Edge[] edge;

}

public static Graph CreateGraph(int verticesCount, int edgesCount)

{

Graph graph = new Graph();

graph.VerticesCount = verticesCount;

graph.EdgesCount = edgesCount;

graph.edge = new Edge[graph.EdgesCount];

return graph;

}

private static void Print(int[] distance, int count)

{

Console.WriteLine("Расстояние до вершины от источника");

for (int i = 0; i < count; ++i)

Console.WriteLine("{0}\t {1}", i, distance[i]);

}

public static void BellmanFord(Graph graph, int source)

{

int verticesCount = graph.VerticesCount;

int edgesCount = graph.EdgesCount;

int[] distance = new int[verticesCount];

for (int i = 0; i < verticesCount; i++)

distance[i] = int.MaxValue;

distance[source] = 0;

for (int i = 1; i <= verticesCount - 1; ++i)

{

for (int j = 0; j < edgesCount; ++j)

{

int u = graph.edge[j].Source;

int v = graph.edge[j].Destination;

int weight = graph.edge[j].Weight;

if (distance[u] != int.MaxValue && distance[u] + weight < distance[v])

distance[v] = distance[u] + weight;

}

for (int i = 0; i < edgesCount; ++i)

{

int u = graph.edge[i].Source;

int v = graph.edge[i].Destination;

int weight = graph.edge[i].Weight;

if (distance[u] != int.MaxValue && distance[u] + weight < distance[v])

Console.WriteLine("Граф содержит цикл отрицательного веса.");

}

Print(distance, verticesCount);

}

static void Main(string[] args)

{

int verticesCount = 5;

int edgesCount = 8;

Graph graph = CreateGraph(verticesCount, edgesCount);

// Edge 0-1

graph.edge[0].Source = 0;

graph.edge[0].Destination = 1;

graph.edge[0].Weight = -1;

// Edge 0-2

graph.edge[1].Source = 0;

graph.edge[1].Destination = 2;

graph.edge[1].Weight = 4;

// Edge 1-2

graph.edge[2].Source = 1;

graph.edge[2].Destination = 2;

graph.edge[2].Weight = 3;

// Edge 1-3

graph.edge[3].Source = 1;

graph.edge[3].Destination = 3;

graph.edge[3].Weight = 2;

// Edge 1-4

graph.edge[4].Source = 1;

graph.edge[4].Destination = 4;

graph.edge[4].Weight = 2;

// Edge 3-2

graph.edge[5].Source = 3;

graph.edge[5].Destination = 2;

graph.edge[5].Weight = 5;

// Edge 3-1

graph.edge[6].Source = 3;

graph.edge[6].Destination = 1;

graph.edge[6].Weight = 1;

// Edge 4-3

graph.edge[7].Source = 4;

graph.edge[7].Destination = 3;

graph.edge[7].Weight = -3;

BellmanFord(graph, 0);

Console.ReadKey();

}

Решение Задачи «Рюкзак» на C#

Приветствую всех, сегодня рассмотрим алгоритм решения задачи «Рюкзак». По условию задания у нас есть набор предметов. У каждого предмета есть вес и цена. Нужно собрать рюкзак, уложившись в предел веса(40 кг) и обеспечив максимальную стоимость содержимого.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Knapsack
{
    class KnapsackAlgorithm
    {
        public static int KnapSack(int capacity, int[] weight, int[] value, int itemsCount)
        {
            int[,] K = new int[itemsCount + 1, capacity + 1];

            for (int i = 0; i <= itemsCount; ++i)
            {
                for (int w = 0; w <= capacity; ++w)
                {
                    if (i == 0 || w == 0)
                        K[i, w] = 0;
                    else if (weight[i - 1] <= w)
                        K[i, w] = Math.Max(value[i - 1] + K[i - 1, w - weight[i - 1]], K[i - 1, w]);
                    else
                        K[i, w] = K[i - 1, w];
                }
            }

            return K[itemsCount, capacity];
        }
        static void Main(string[] args)
        {
            int[] value = { 10, 50, 70 };
            int[] weight = { 10, 20, 30 };
            int capacity = 40;
            int itemsCount = 3;

            int result = KnapSack(capacity, weight, value, itemsCount);
            Console.WriteLine(result);
            Console.ReadKey();
        }
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace Knapsack

{

class KnapsackAlgorithm

{

public static int KnapSack(int capacity, int[] weight, int[] value, int itemsCount)

{

int[,] K = new int[itemsCount + 1, capacity + 1];

for (int i = 0; i <= itemsCount; ++i)

{

for (int w = 0; w <= capacity; ++w)

{

if (i == 0 || w == 0)

K[i, w] = 0;

else if (weight[i - 1] <= w)

K[i, w] = Math.Max(value[i - 1] + K[i - 1, w - weight[i - 1]], K[i - 1, w]);

else

K[i, w] = K[i - 1, w];

}

return K[itemsCount, capacity];

}

static void Main(string[] args)

{

int[] value = { 10, 50, 70 };

int[] weight = { 10, 20, 30 };

int capacity = 40;

int itemsCount = 3;

int result = KnapSack(capacity, weight, value, itemsCount);

Console.WriteLine(result);

Console.ReadKey();

}

Реализуем Алгоритм Грубой Силы «BruteForce» на C#

Приветствую всех! Многие из вас встречали утилиты по BruteForce, а сегодня мы с вами его сами напишем и рассмотрим его реализацию. Грубый поиск или исчерпывающий поиск, также известный как генерация, подбор символов и тестирование, является очень общим методом решения проблем, который состоит из систематического перечисления всех возможных вариантов решение и проверки того, удовлетворяет ли каждый […]

Новые записи →