public class Node
{
    public char name;           // 节点名称
    public Node[] childs;   // 所有连接节点
    public Node(char name, Node[] childs = null) { this.name = name; this.childs = childs; }
}

public class NodeValue
{
    public char name;       // 节点名称
    public int val;         // 到当前节点的最短路径
    public NodeValue pre;   // 前置节点
    public NodeValue(char name, int val) { this.name = name; this.val = val; }
}

// 节点
Dictionary<char, Node> nodeDict = null;
// 权重
Dictionary<string, int> weightDict = null;

Action initData = () =>
{
    Node A = new Node('A');
    Node B = new Node('B');
    Node C = new Node('C');
    Node D = new Node('D');
    Node E = new Node('E');
    Node F = new Node('F');
    Node G = new Node('G');

    A.childs = new Node[] { B, F, G };
    B.childs = new Node[] { A, F, C };
    C.childs = new Node[] { B, F, E, D };
    D.childs = new Node[] { C, E };
    E.childs = new Node[] { D, C, F, G };
    F.childs = new Node[] { A, B, C, E, G };
    G.childs = new Node[] { A, F, E };

    nodeDict = new Dictionary<char, Node>()
    {
        { A.name, A }, { B.name, B }, { C.name, C }, { D.name, D }, { E.name, E }, { F.name, F }, { G.name, G }
    };

    weightDict = new Dictionary<string, int>()
    {
        {"A_B",12 },{"A_F",16 },{"A_G",14 },
        {"B_A",12 },{"B_F", 7 },{"B_C",10 },
        {"C_B",10 },{"C_F", 6 },{"C_E",5 },{"C_D",3 },
        {"D_C", 3 },{"D_E", 4 },
        {"E_D", 4 },{"E_C", 5 },{"E_F",2 },{"E_G",8 },
        {"F_A",16 },{"F_B", 7 },{"F_C",6 },{"F_E",2 },{"F_G",9 },
        {"G_A",14 },{"G_F", 9 },{"G_E",8 },
    };
};

initData();

// 代表正无穷
private const int MAX_INTEGER = int.MaxValue;

// 根据名字从列表中找到节点
private static NodeValue GetNodeByName(List<NodeValue> nodeList, char name)
{
    NodeValue result = null;
    nodeList.ForEach((tmp) => { if (tmp.name == name) result = tmp; });
    return result;
}

// 计算两个节点之间的权重
private static int GetNodeWeight(Dictionary<string, int> weightDict,  Node node1, Node node2)
{
    string key = $"{node1.name}_{node2.name}";
    if (weightDict.ContainsKey(key)) return weightDict[key];

    return MAX_INTEGER;
}

// 获取列表中权重最小的节点
private static NodeValue GetMinWeightNode(List<NodeValue> nodeList)
{
    NodeValue tmp = nodeList[0];
    nodeList.ForEach((item) => { tmp = item.val < tmp.val ? item : tmp; });
    return tmp;
}

// 刷新节点的子节点在U中到各个节点的权重
private static void RefreshChildNodeWeightInU(Dictionary<char, Node> nodeDict, Dictionary<string, int> weightDict, List<NodeValue> nodeListU, NodeValue node)
{
    var childs = nodeDict[node.name].childs;
    for (int i = 0, iMax = childs.Length; i < iMax; i++)
    {
        int w = GetNodeWeight(weightDict, nodeDict[node.name], nodeDict[childs[i].name]);
        NodeValue v = GetNodeByName(nodeListU, childs[i].name);
        if (v == null) continue;

        if (node.val + w < v.val)
        {
            v.val = w + node.val;
            v.pre = node;
        }
    }
}


public static List<NodeValue> Dijkstra(Dictionary<char, Node> nodeDict, Dictionary<string, int> weightDict, char startName)
{
    // S表 记录已计算出最短路径的列表
    List<NodeValue> S = new List<NodeValue>(nodeDict.Count);
    // S表 记录未计算出最短路径的列表
    List<NodeValue> U = new List<NodeValue>(nodeDict.Count);

    // 打印日志
    Action print = () =>
    {
        Console.Write("S\t{ ");
        foreach (NodeValue item in S) { Console.Write($"[{item.name}: {item.val}], "); }
        Console.WriteLine(" }");


        Console.Write("U\t{ ");
        foreach (NodeValue item in U)
        {
            string result = item.val.ToString();
            if (item.val == MAX_INTEGER) result = "∞";
            Console.Write($"[{item.name}: {result}], ");
        }
        Console.WriteLine(" }");
        Console.WriteLine("-----------------------------------------");
    };

    #region 起始点

    // 起始节点，加入S表
    // 其余节点，加入U表
    NodeValue startNode = new NodeValue(startName, 0);
    S.Add(startNode);
    foreach (var node in nodeDict)
    {
        if (node.Key == startName) continue;
        int w = GetNodeWeight(weightDict, nodeDict[node.Key], nodeDict[startName]);
        NodeValue item = new NodeValue(node.Key, w);
        if (w != MAX_INTEGER) item.pre = startNode;
        U.Add(item);
    }
    // 打印日志
    print();
    #endregion


    #region 所有节点
    while (S.Count < nodeDict.Count)
    {
        NodeValue node = GetMinWeightNode(U);
        RefreshChildNodeWeightInU(nodeDict, weightDict, U, node);
        U.Remove(node);
        S.Add(node);

        // 打印日志
        print();
    }
    #endregion

    return S;
}

static void Main(string[] args)
{
    // 开始节点为：'D'
    char startName = 'D';
    List<NodeValue> list = Dijkstra(nodeDict, weightDict, startName);

    // 输出展示
    while (true)
    {
        Console.Write("输入结束节点：");
        string str = Console.ReadLine();
        if (string.IsNullOrWhiteSpace(str)) continue;

        NodeValue node = GetNodeByName(list, str[0]);
        if (node != null)
        {
            NodeValue tmp = node;
            while (tmp.pre != null)
            {
                Console.Write(tmp.name + "<--");
                tmp = tmp.pre;
            }
            Console.WriteLine(startName);
        }
    }
}