Program.cs

using System;
using System.Collections.Generic;
using System.Data.SqlClient;



public class Graph
{

    private Dictionary<string, List<(string to, double Distance)>> adjacencyList = new();
    //List<(string to, double Distance) this is tuble


    private void Add_Node(string place)
     {

         if(!adjacencyList.ContainsKey(place))
         {
            adjacencyList[place] = new List<(string to, double Distance)>();
         }
        // adjacencyList[place] the key of node
        //new List<(string to, double Distance)>(); the value of the key 

    }
    public void Add_Edge(string from , string to, double Distance)
    {

        Add_Node(from);
        adjacencyList[from].Add((to, Distance));
    }


    public Dictionary<string, List<(string to, double Distance)>> GetadjacencyList()
    {
        return adjacencyList; 
    }
    // abliy the encabsulation
};


public static class GraphLoader
{
    
    public static Graph LoeadEdgsFromDatabase()
    {
        Graph graph = new Graph();


        string connectionString = "Data Source=DESKTOP-JVK01UB;Initial Catalog=DBmaps;Integrated Security=True;";


        using SqlConnection connection = new SqlConnection(connectionString);
        connection.Open();


        string query = "select [FromGovernorate], [ToGovernorate] ,[DistanceKm]  from [DirectGovernorateLinks]";

        using SqlCommand command = new SqlCommand(query, connection);

        using SqlDataReader reader = command.ExecuteReader();


        while (reader.Read())
        {
            string from = reader.GetString(0);
            string to = reader.GetString(1);
            double distance = reader.GetDouble(2);

            graph.Add_Edge(from, to, distance);
        }
        return graph;

    }


};


public static class Dijkstra
{


    public static (Dictionary<string, double> distance, Dictionary<string, string> previous) ComputeShortestPaths(Graph graph, string start)
    {



        var distance = new Dictionary<string, double>();
        var previous = new Dictionary<string, string>();
        var visited = new HashSet<string>();
        var pirority = new PriorityQueue<string, double>();




         
         foreach(var node in graph.GetadjacencyList().Keys)
         {

            distance[node] = double.PositiveInfinity;
            previous[node] = null;

         }


        distance[start] = 0;
        pirority.Enqueue(start, 0);

        //this is handle the  neighbors in the one node and get the piroity
        while (pirority.Count > 0)
        {

            var currentNode = pirority.Dequeue();

            if (visited.Contains(currentNode))
                continue;


            visited.Add(currentNode);


            if(!graph.GetadjacencyList().ContainsKey(currentNode))
            {
                continue;
            }



            foreach(var (neighbor, distantofneighbor) in graph.GetadjacencyList()[currentNode])
            {

                double newdistanse = distance[currentNode] + distantofneighbor;

                if(newdistanse < distance.GetValueOrDefault(neighbor,double.PositiveInfinity))//comber the newdistanc in the new path & the dist in the neighbor
                {

                    distance[neighbor] = newdistanse;
                    previous[neighbor] = currentNode;//like this
                                                     //"Aswan": "Luxor",
                                                     //"Luxor": "Qena",
                                                     //"Qena": "Sohag",
                                                     //"Sohag": "Cairo";

                pirority.Enqueue(neighbor, newdistanse);
                }

            }


        }

        return (distance, previous);

    }

    public static List<string> ReconstructPath(Dictionary<string, string> preivus, string end, string start)
    {

        string current = end;

        List<string> path = new List<string>();
        while (current != null)
        {
            path.Insert(0, current);
            current = preivus[current];
        }

        if(path.Count == 0 || path[0] != start)
        {
            return new List<string>();
        }

        return path;
    }
};


class Program
{
    static void Main(string[] args)
    {

        Graph graph = new Graph();

        graph = GraphLoader.LoeadEdgsFromDatabase();

        string start = "Cairo";
        string end = "Aswan";


        //Tuple Deconstruction
        var (distance,prevuse) =  Dijkstra.ComputeShortestPaths(graph, start);


        if(distance.ContainsKey(end))
        {

            Console.WriteLine($"the shortesh path from {start} to {end} = {distance[end]} km");

             List<string> path = Dijkstra.ReconstructPath(prevuse,end,start);

            Console.WriteLine($"the path from {start} to {end} is   {string.Join("->", path)}");
        }
        else
        {
            Console.WriteLine($"No path found from {start} to {end}..");
        }
    }
}