利用向量积来进行判断。若为凸多边形，则依次遍历所有顶点，相邻三个顶点所构成的两个向量的向量积的方向都一致；当为凹时，则方向会相反，此时，就可以判断多边形的凸凹性。
参考公式：

利用向量积进行判断。若相等，则所有顶点对应的向量积(每个顶点的两边视为该顶点的两个向量)应相等。

C实现，Python实现。

该算法可视为Dijkstor算法的一个改进。D算法解决了有向正权图的最短路径问题，但它无法处理负权路径问题。

最短路径中不能包含负权回路，因为每次经过负权回路，路径的权值会减少，所以这种情况下不存在最短路径。

有些图结构中会存在负权边，用于表达通过某条路径可以降低总消耗，在有向图中，负权边不一定会形成负权回路，所以在一些计算最短路径算法中，负权边也可以计算出最短路径。

在无向图中，负权边就意味着负权回路，所以无向图中不能存在负权边。所有最短路径的讨论假设不存在负权回路。

B算法解决了两个问题：
第一个，带有负权的最短路径问题；
第二个，假设图中最多有N个节点，给定源节点后，最多N-1次松弛迭代，即可找出全部的从源节点到所有节点的最短路径。如果超过N-1次，仍然存在有未找到最短路径的节点，则该图存在负权回路。因此，B算法可以进行负权回路检测。