图解最短路径问题 Dijkstra Floyd，纯手绘图_最短路径怎么画

Dijkstra:

• 算法思想: 从某个源点到各个点的最短路径。将各顶点与v0间的最短路径。按路径长度递增次序，产生最短路径算法。
  这样说可能很抽象，结合一下图来看可能会更好理解。

• 集合S表示从v0开始到集合s内的点，已找到最短路径。T表示未找到最短路径的点。在整个带权有向图中，只要找到v0到T集合中最短路径的点，就把该点收到S集合中。

• 第一轮，v0被收入S集合中，其他点都在T中。此时需要找v0到T各个点的最短路径。由下图1表格根据有向图的权值画的图可知，v0->v2最小。v2加入S中。

• 第二轮，图二，当v2加入s时，看看有没有路径是由v0出发，通过v2到达的点。由图可知，v3此时有路了，v0->v2->v3=60, 而v4和v5没有因为v2的加入从v0到达的权值更小(如果经过v2反而更大了)，因此权值不改，原来的路径不改(图中↓表示路径不改，直接用上一轮的路径)。此时比较最短路径，v4最小，v4加入S中。

• 重复以上步骤，三四五轮后，所有点都在S中了，此时所有最短路径找到了。

因为博主时间有限，先把书上的代码放这。之后有时间会自己写一遍编辑过来的。(以下选自严蔚敏数据结构)


Floyd算法:

• 算法思想: 求两个点的最短距离。通过在图中加入中间点来找两个点间的最短路径。
  用邻接矩阵存储，直接上代码会更好理解，如果那里有不太懂的地方可以DM我。
  
  在三层循环这，K一定要在最外层，具体原因建议看看其他博主是怎么解释，这里就不过多解释了

leedcode 104. 二叉树的最大深度(DFS)用递归栈实现

int maxDepth(struct TreeNode* root){
    TreeNode *p;//头结点
    int num =0;
    
    p = root;
    if(p != NULL && p->left == NULL && P->right == NULL )//只有一个节点
    {
        num == 1;
    }
    else if(p ==NULL)
    {
        num == 0;
    }
    else
    {
        if(p -> left != NULL)//左孩子不为空
        {
            p = p -> left;
            maxDepth(P);
        }
        if(p ->right != NULL)//右孩子不为空
        {
            p  = p ->right;
            maxDepth(p);
        }
        num++
    }
    return num;
}
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