Τι Είναι ο Αλγόριθμος του Dijkstra;

Φαντάσου ότι είσαι σε ένα μεγάλο λαβύρινθο με πολλούς δρόμους και θες να βρεις την πιο σύντομη διαδρομή για να φτάσεις από την είσοδο στην έξοδο. Ο Αλγόριθμος του Dijkstra είναι σαν έναν έξυπνο βοηθό που μπορεί να βρει την πιο σύντομη διαδρομή για εσένα.

Πώς Λειτουργεί:

Ξεκινάς από ένα Σημείο:
- Ο αλγόριθμος του Dijkstra ξεκινά από ένα αρχικό σημείο ή κόμβο (όπως την είσοδο του λαβυρίνθου) και θέλει να βρει την πιο σύντομη διαδρομή μέχρι όλα τα άλλα σημεία στον λαβύρινθο.

Εξετάζει Όλους τους Δρόμους:
- Αρχικά, ο αλγόριθμος υπολογίζει τη μικρότερη απόσταση από το αρχικό σημείο σε όλους τους γειτονικούς κόμβους (όπως τους γείτονες της εισόδου).

Επιλέγει την Κοντινότερη Οδό:
- Στη συνέχεια, από όλους τους γειτονικούς κόμβους, επιλέγει τον κόμβο με την πιο μικρή απόσταση και εξετάζει τους δικούς του γείτονες για να δει αν μπορεί να βρει μια ακόμα πιο κοντινή διαδρομή.

Επαναλαμβάνει τη Διαδικασία:
- Επαναλαμβάνει τη διαδικασία, επιλέγοντας πάντα τον κόμβο με την πιο κοντινή απόσταση και εξετάζοντας τους γείτονές του μέχρι να εξετάσει όλους τους κόμβους.

Βρίσκει την Πιο Σύντομη Διαδρομή:
- Όταν ολοκληρωθεί η διαδικασία, έχεις την πιο σύντομη διαδρομή από την είσοδο σε όλα τα άλλα σημεία στον λαβύρινθο.

Παράδειγμα στον Κόσμο των Γραφημάτων

Φαντάσου το λαβύρινθο ως ένα γράφο με κόμβους και δρόμους. Κάθε δρόμος έχει έναν αριθμό που δείχνει πόσο μακριά είναι. Ο Αλγόριθμος του Dijkstra θα βρει την πιο σύντομη διαδρομή από έναν κόμβο (όπως την είσοδο) σε όλους τους άλλους κόμβους, έτσι ώστε να γνωρίζεις πόσο χρόνο ή απόσταση χρειάζεται για να φτάσεις από την είσοδο σε οποιοδήποτε άλλο σημείο.

Πώς Το Χρησιμοποιούμε στην C#

Ας δούμε πώς θα μπορούσαμε να εφαρμόσουμε τον Αλγόριθμο του Dijkstra στην C#. Θα χρησιμοποιήσουμε μια απλή έκδοση του αλγορίθμου για να βρούμε την πιο σύντομη διαδρομή σε έναν γράφο.

Δημιουργούμε τον Γράφο:
- Ο γράφος μπορεί να αναπαριστάται ως ένα σύνολο κόμβων με δρόμους που τους συνδέουν.

Εφαρμόζουμε τον Αλγόριθμο:
- Χρησιμοποιούμε μια δομή δεδομένων για να κρατήσουμε τις αποστάσεις και τις διαδρομές.

Εκτυπώνουμε τα Αποτελέσματα:
- Εμφανίζουμε την πιο σύντομη απόσταση και τις διαδρομές από τον αρχικό κόμβο σε όλους τους άλλους κόμβους.

Ακολουθεί ένας απλός τρόπος να το κάνουμε στην C#:

using System;
using System.Collections.Generic;

public class Program
{
    // Στρατηγική για να κρατάμε τις αποστάσεις
    static Dictionary<int, int> distances = new Dictionary<int, int>();

    // Στρατηγική για να κρατάμε τους γείτονες
    static Dictionary<int, List<Tuple<int, int>>> graph = new Dictionary<int, List<Tuple<int, int>>>();

    public static void Main()
    {
        // Δημιουργούμε τον γράφο
        graph[1] = new List<Tuple<int, int>> { Tuple.Create(2, 1), Tuple.Create(3, 4) };
        graph[2] = new List<Tuple<int, int>> { Tuple.Create(3, 2), Tuple.Create(4, 5) };
        graph[3] = new List<Tuple<int, int>> { Tuple.Create(4, 1) };
        graph[4] = new List<Tuple<int, int>>();

        // Εκτελούμε τον αλγόριθμο του Dijkstra
        Dijkstra(1);

        // Εκτυπώνουμε τα αποτελέσματα
        foreach (var kvp in distances)
        {
            Console.WriteLine($"Απόσταση από 1 στο {kvp.Key} είναι {kvp.Value}");
        }
    }

    public static void Dijkstra(int start)
    {
        // Αρχικοποιούμε τις αποστάσεις
        foreach (var node in graph.Keys)
        {
            distances[node] = int.MaxValue;
        }
        distances[start] = 0;

        // Δημιουργούμε μια λίστα για να κρατήσουμε τους κόμβους που εξετάζουμε
        var priorityQueue = new SortedSet<Tuple<int, int>>(Comparer<Tuple<int, int>>.Create((a, b) => a.Item2.CompareTo(b.Item2)));
        priorityQueue.Add(Tuple.Create(start, 0));

        while (priorityQueue.Count > 0)
        {
            var current = priorityQueue.Min;
            priorityQueue.Remove(current);

            int currentNode = current.Item1;
            int currentDistance = current.Item2;

            if (currentDistance > distances[currentNode])
            {
                continue;
            }

            foreach (var neighbor in graph[currentNode])
            {
                int neighborNode = neighbor.Item1;
                int edgeWeight = neighbor.Item2;
                int newDistance = currentDistance + edgeWeight;

                if (newDistance < distances[neighborNode])
                {
                    distances[neighborNode] = newDistance;
                    priorityQueue.Add(Tuple.Create(neighborNode, newDistance));
                }
            }
        }
    }
}

Εξήγηση Κώδικα:

Δημιουργούμε τον Γράφο:
- Έχουμε έναν γράφο με κόμβους και συνδέσμους (με βάρη).

Αρχικοποιούμε τις Αποστάσεις:
- Θέτουμε τις αποστάσεις σε όλους τους κόμβους ως “άπειρες” εκτός από την αρχική θέση που είναι 0.

C# Learning

Dijkstra’s Algorithm

Τι Είναι ο Αλγόριθμος του Dijkstra;

Πώς Λειτουργεί:

Παράδειγμα στον Κόσμο των Γραφημάτων

Πώς Το Χρησιμοποιούμε στην C#

Εξήγηση Κώδικα: