Ekzamen111/Ekz/Program.cs

using System;
using System.Diagnostics;
using System.IO;

namespace DejkstraAlgorithm1
{
    public class DejkstraAlgorithm
    {

        public static int V = 5;


        public static int MinDistance(int[] dist, bool[] sptSet)
        {
            int min = int.MaxValue, min_index = -1;

            for (int v = 0; v < V; v++)
            {
                if (!sptSet[v] && dist[v] <= min)
                {
                    min = dist[v];
                    min_index = v;
                }
            }

            return min_index;
        }


        public static void PrintSolution(int[] dist)
        {
            Console.WriteLine("Вершина \t Расстояние от вершины 1");
            for (int i = 0; i < V; i++)
            {
                Console.WriteLine(i + 1 + "\t \t \t" + dist[i]);
            }
        }

        public static int[] Dejkstra(int[,] graph, int src)
        {
            int[] dist = new int[V];
            bool[] sptSet = new bool[V];

            for (int i = 0; i < V; i++)
            {
                dist[i] = int.MaxValue;
                sptSet[i] = false;
            }

            dist[src] = 0;

            for (int i = 0; i < V - 1; i++)
            {
                int u = MinDistance(dist, sptSet);
                sptSet[u] = true;

                for (int v = 0; v < V; v++)
                {
                    if (!sptSet[v] && graph[u, v] != 0 && dist[u] != int.MaxValue && (dist[u] + graph[u, v] < dist[v]))
                    {
                        dist[v] = dist[u] + graph[u, v];
                    }
                }
            }

            PrintSolution(dist);
            return dist;
        }


        public static void Main()
        {
            int[,] graph = new int[,] {
            { 0, 4, 6, 7,0},
            { 4, 0, 0, 0,8},
            { 6, 0, 0, 1,2},
            { 7, 0, 1, 0,5},
            { 0, 8, 2, 5,0},

        };


            int[] c = Dejkstra(graph, 0);

            Trace.Listeners.Add(new TextWriterTraceListener(File.Open("trace.txt", FileMode.OpenOrCreate)));
            Trace.AutoFlush = true;
            Trace.WriteLine("Program complete");
        }

    }
}