I have a requirement to implement a sophisticated algorithm in C# that can effectively determine the shortest path between nodes in a weighted graph. The graph structure is based on adjacency lists, which efficiently represent connections between nodes. One of the challenges I face is accommodating scenarios where the graph may include edges with negative weights. This requires careful consideration to ensure the algorithm can handle such weights while still computing the shortest path correctly:

using System.Collections.Generic;

public class ShortestPathAlgorithm
{
    private Dictionary<int, List<(int, int)>> graph;

    public ShortestPathAlgorithm(Dictionary<int, List<(int, int)>> graph)
    {
        this.graph = graph;
    }

    public List<int> FindShortestPath(int startNode, int endNode)
    {
        Dictionary<int, int> distances = InitializeDistances(startNode);
        Dictionary<int, int?> previousNodes = InitializePreviousNodes();
        List<int> unvisitedNodes = new List<int>(graph.Keys);

        while (unvisitedNodes.Count > 0)
        {
            int currentNode = GetClosestNode(unvisitedNodes, distances);
            unvisitedNodes.Remove(currentNode);

            foreach (var (neighbor, weight) in graph[currentNode])
            {
                int alternativeRoute = distances[currentNode] + weight;
                if (alternativeRoute < distances[neighbor])
                {
                    distances[neighbor] = alternativeRoute;
                    previousNodes[neighbor] = currentNode;
                }
            }
        }

        return BuildPath(startNode, endNode, previousNodes);
    }

    private Dictionary<int, int> InitializeDistances(int startNode)
    {
        Dictionary<int, int> distances = new Dictionary<int, int>();
        foreach (var node in graph.Keys)
        {
            distances[node] = int.MaxValue;
        }
        distances[startNode] = 0;
        return distances;
    }

    private Dictionary<int, int?> InitializePreviousNodes()
    {
        Dictionary<int, int?> previousNodes = new Dictionary<int, int?>();
        foreach (var node in graph.Keys)
        {
            previousNodes[node] = null;
        }
        return previousNodes;
    }

    private int GetClosestNode(List<int> unvisitedNodes, Dictionary<int, int> distances)
    {
        int minDistance = int.MaxValue;
        int closestNode = -1;

        foreach (var node in unvisitedNodes)
        {
            if (distances[node] < minDistance)
            {
                minDistance = distances[node];
                closestNode = node;
            }
        }

        return closestNode;
    }

    private List<int> BuildPath(int startNode, int endNode, Dictionary<int, int?> previousNodes)
    {
        List<int> shortestPath = new List<int>();
        int? currentNodePath = endNode;

        while (currentNodePath != null)
        {
            shortestPath.Add(currentNodePath.Value);
            currentNodePath = previousNodes[currentNodePath.Value];
        }

        shortestPath.Reverse();
        return shortestPath;
    }

    public static void Main(string[] args)
    {
        var graph = new Dictionary<int, List<(int, int)>>()
        {
            { 1, new List<(int, int)>{ (2, 7), (3, 9), (6, 14) } },
            { 2, new List<(int, int)>{ (1, 7), (3, 10), (4, 15) } },
            { 3, new List<(int, int)>{ (1, 9), (2, 10), (4, 11), (6, 2) } },
            { 4, new List<(int, int)>{ (2, 15), (3, 11), (5, 6) } },
            { 5, new List<(int, int)>{ (4, 6), (6, 9) } },
            { 6, new List<(int, int)>{ (1, 14), (3, 2), (5, 9) } }
        };

        var algorithm = new ShortestPathAlgorithm(graph);
        var shortestPath = algorithm.FindShortestPath(1, 5);

        Console.WriteLine("Shortest Path from Node 1 to Node 5:");
        Console.WriteLine(string.Join(" -> ", shortestPath));
    }
}```