Реализация алгоритма Дейкстры при помощи ChatGPT (GPT-4)

dijkstra-chatgpt4.md

ChatGPT-4 example

Tagir Magomedov:

Напиши функцию на C#, которая выполняет поиск пути во взвешенном ориентированном графе.

ChatGPT:

Для поиска кратчайшего пути во взвешенном ориентированном графе, одним из популярных алгоритмов является алгоритм Дейкстры. Вот пример реализации алгоритма Дейкстры на C#:

using System;
using System.Collections.Generic;

class Graph
{
    private int vertices;
    private List<Tuple<int, int>>[] adjList;

    public Graph(int vertices)
    {
        this.vertices = vertices;
        adjList = new List<Tuple<int, int>>[vertices];
        for (int i = 0; i < vertices; ++i)
            adjList[i] = new List<Tuple<int, int>>();
    }

    public void AddEdge(int source, int destination, int weight)
    {
        adjList[source].Add(new Tuple<int, int>(destination, weight));
    }

    public void Dijkstra(int source, int destination)
    {
        int[] distances = new int[vertices];
        bool[] processed = new bool[vertices];
        int[] previous = new int[vertices];

        for (int i = 0; i < vertices; ++i)
        {
            distances[i] = int.MaxValue;
            processed[i] = false;
            previous[i] = -1;
        }

        distances[source] = 0;
        for (int i = 0; i < vertices - 1; ++i)
        {
            int u = FindMinDistance(distances, processed);
            processed[u] = true;

            foreach (var neighbor in adjList[u])
            {
                int v = neighbor.Item1;
                int weight = neighbor.Item2;
                if (!processed[v] && distances[u] != int.MaxValue && distances[u] + weight < distances[v])
                {
                    distances[v] = distances[u] + weight;
                    previous[v] = u;
                }
            }
        }

        PrintPath(previous, destination);
        Console.WriteLine($"Shortest path length: {distances[destination]}");
    }

    private int FindMinDistance(int[] distances, bool[] processed)
    {
        int min = int.MaxValue;
        int minIndex = -1;

        for (int v = 0; v < vertices; ++v)
        {
            if (!processed[v] && distances[v] < min)
            {
                min = distances[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    private void PrintPath(int[] previous, int destination)
    {
        if (previous[destination] == -1)
        {
            Console.Write($"{destination} ");
            return;
        }

        PrintPath(previous, previous[destination]);
        Console.Write($"{destination} ");
    }
}

class Program
{
    static void Main(string[] args)
    {
        Graph g = new Graph(6);
        g.AddEdge(0, 1, 5);
        g.AddEdge(0, 2, 3);
        g.AddEdge(1, 3, 6);
        g.AddEdge(1, 2, 2);
        g.AddEdge(2, 4, 4);
        g.AddEdge(2, 5, 6);
        g.AddEdge(2, 3, 7);
        g.AddEdge(3, 5, 1);
        g.AddEdge(3, 4, 5);
        g.AddEdge(4, 5, 2);

        int source = 0;
        int destination = 5;
        Console.WriteLine($"Shortest path from {source} to {destination}:");
        g.Dijkstra(source, destination);
    }
}

Tagir Magomedov:

Объясни код

ChatGPT:

Данный код реализует алгоритм Дейкстры для поиска кратчайшего пути во взвешенном ориентированном графе. Сначала создается класс Graph с полями для хранения количества вершин и списка смежности.

1. Конструктор Graph(int vertices): Инициализирует граф с заданным количеством вершин и инициализирует список смежности для каждой вершины.
2. Метод AddEdge(int source, int destination, int weight): Добавляет ребро с заданным весом от вершины source к вершине destination.
3. Метод Dijkstra(int source, int destination): Выполняет алгоритм Дейкстры для поиска кратчайшего пути от вершины source к вершине destination. Расстояния между вершинами хранятся в массиве distances, а массив previous хранит предыдущие вершины для каждой вершины в кратчайшем пути.
4. Метод FindMinDistance(int[] distances, bool[] processed): Возвращает вершину с минимальным расстоянием, которая еще не была обработана.
5. Метод PrintPath(int[] previous, int destination): Рекурсивно печатает кратчайший путь от исходной вершины до вершины destination с использованием массива previous.

В главной функции Main создается экземпляр графа с 6 вершинами, добавляются ребра между ними, затем вызывается метод Dijkstra для поиска кратчайшего пути между вершинами 0 и 5. В результате работы программы выводится кратчайший путь между указанными вершинами и его длина.