默然的博客
TonyChenn 的游戏客户端开发博客，记录 Cocos2d-x、C#、Unity、Win32 与鸿蒙开发中的源码分析、性能优化和工程实践。
 默然的博客
facebook QQ twitter weibo telegram linkedin

算法-迪杰斯特拉(Dijkstra)

一言加载中...

发布于 更新于

简介

迪杰斯特拉（Dijkstra）。是一个典型的计算最短路径算法。用来计算图中一个节点到另一个节点间的最短路径。其特点是从起始点开始向四周扩散，最后遍历完所有节点结束。属于广度搜索。

思想

  1. 对于一个有权重的图G,指定一个起点A。
  2. 列表S记录已计算出最短路径的点；列表U记录未计算出最短路径的点。
  3. 从起点A出发。S中只记录点A,距离为0；列表U中记录所有节点到A点的距离，如果不相邻则记为无穷大。
  4. 从列表U中选出路径最小的点B，从S表中移除，并加入表U，同时更新U表中到起点A的距离。
  5. 重复操作，直到U表为空，遍历完所有节点结束。

过程

PS：图片出自：鹅厂程序小哥的知乎文章
dijkstra.png

代码实现

基本数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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; }
}

初始化节点数据与节点间权重数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 节点
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();

核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
// 代表正无穷
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;
}

测试执行一波波:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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);
        }
    }
}

结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
S       { [D: 0],  }
U       { [A: ∞], [B: ∞], [C: 3], [E: 4], [F: ∞], [G: ∞],  }
-----------------------------------------
S       { [D: 0], [C: 3],  }
U       { [A: ∞], [B: 13], [E: 4], [F: 9], [G: ∞],  }
-----------------------------------------
S       { [D: 0], [C: 3], [E: 4],  }
U       { [A: ∞], [B: 13], [F: 6], [G: 12],  }
-----------------------------------------
S       { [D: 0], [C: 3], [E: 4], [F: 6],  }
U       { [A: 22], [B: 13], [G: 12],  }
-----------------------------------------
S       { [D: 0], [C: 3], [E: 4], [F: 6], [G: 12],  }
U       { [A: 22], [B: 13],  }
-----------------------------------------
S       { [D: 0], [C: 3], [E: 4], [F: 6], [G: 12], [B: 13],  }
U       { [A: 22],  }
-----------------------------------------
S       { [D: 0], [C: 3], [E: 4], [F: 6], [G: 12], [B: 13], [A: 22],  }
U       {  }
-----------------------------------------
输入结束节点：A
A<--F<--E<--D
输入结束节点：B
B<--C<--D
输入结束节点：C
C<--D
输入结束节点：D
D
输入结束节点：E
E<--D
输入结束节点：F
F<--E<--D
输入结束节点：G
G<--E<--D

相关阅读

赏 支付宝 微信 关闭
算法-A星寻路 算法-链表专题 算法-单链表反转 算法-计算文件夹B相对文件夹A的相对路径

评论