有向图d算法

① 用来求解加权有向图的最短路径的算法是什么算法

单元最短路径：
1.如果没有负权环的稀疏图，可以用SPFA，时间复杂度O（KM）
M是边数，K是平均入队列的次数
2.如果没有负权环的稠密图，建议用Dijkstra O（N^2），用二叉堆可优化到
O（NlogN），斐波那契堆编程复杂度太高，不易于实现
3.如果有负权环，可以尝试floyd,O(n^3)

任两点最短路径：floyd较好实现，基于重标号johnson也不错（稀疏图效率高）
具体程序可以上网查

② 已知带权有向图如图7-29所示,请利用Dijkstra算法从顶点V4出发到其余顶点的最短路

初始化d[i]为无穷大，由于从v4开始，所以将d4=0，标记v4已选择。
下面开始Dijkstra算法：
和v4相连的且未标记的点有v2和v6，这样更新d2=20，d6=15，选择未标记所有点中最小的d6=15，标记v6已选择，这样我们算出了v4->v6最短距离d6=15；
从v6开始，和v6相连的且未标记的是v2，此时算d6+6=21>20,所以不更新d2，选择未标记所有点中最小的d2=20，标记v2已选择，这样算出了v4->v2最短距离d2=20；
从v2开始，和v2相连的且未标记的有v1和v5，d1=d2+10=30,d5=d2+30=50，选择未标记所有点中最小的d1=30，标记v1已选择，这样我们算出了v4->v1最短距离d1=30；
从v1开始，和v1相连的且未标记的有v3，d3=d1+15=45，选择剩下没被选的所有点的最小的d3=45(d5=50)，标记v3已选择，这样我们算出了v4->v3最短距离d3=45
从v3开始，没有出去的路径，不更新距离，选择剩下没被选的所有点的最小的d5=50，标记v5已选择，这样我们算出了v4->v5最短距离d5=50.
此时所有的点都被访问，结束。
注：上面的标记点已选择注意下，在算法的实现中用的是将所有的点放入队列中，一旦一个点被选择就是说求出了最短距离，就从此队列删除该点，一直到此队列为空，结束算法，我写标记只是为了方便理解。
希望能帮你清晰了解Dijkstra算法，图论中很重要的算法之一。