Реализация алгоритма 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();

}

Добавить комментарий Отменить ответ