【算法基础实验】图论-BellmanFord最短路径

理论知识

Bellman-Ford 和 Dijkstra 是两种用于计算加权图中最短路径的算法，它们在多个方面存在不同之处。下面是它们之间的主要区别：

1. 边权重的处理

Bellman-Ford：
- 能够处理带有负权重边的图，且可以检测负权重环（负权重环是指图中包含一个环，其边权重的总和为负数）。
- 适合解决负权重边的最短路径问题，因为它能够正确计算含负权重的图中的最短路径。
Dijkstra：
- 只能处理非负权重边的图。如果图中有负权重边，Dijkstra 不能保证结果正确。
- Dijkstra 通过优先队列选择当前距离最短的顶点，因此依赖于边权重为正的前提。

2. 算法复杂度

Bellman-Ford：
- 时间复杂度为 O(V * E)，其中 V 是顶点数，E 是边数。
- Bellman-Ford 的效率较低，因为它必须对每条边进行多次松弛操作（V-1 轮）。适合于边数较少或需要处理负权重边的情况。
Dijkstra：
- 时间复杂度为 O(V * logV + E * logV)，其中 V 是顶点数，E 是边数（当使用优先队列实现时，如二叉堆）。
- Dijkstra 更高效，特别是对于稠密图（边数多于顶点数的图）效果更好。

3. 处理负权重环

Bellman-Ford：
- 可以检测负权重环。如果在 V-1 轮松弛操作之后，仍然有可以进一步松弛的边，就说明图中存在负权重环。
- 当图中有负权重环时，Bellman-Ford 能够检测并报告这个环，确保结果的准确性。
Dijkstra：
- 无法处理负权重环。对于负权重环，Dijkstra 不仅无法正确计算最短路径，还可能陷入死循环或返回错误的结果。

4. 贪心与动态规划

Bellman-Ford：
- 属于 动态规划 算法，通过多次迭代逐步逼近最短路径，适合处理负权重的情况。
- 它在每次迭代中松弛所有的边，而不是像贪心算法那样选择当前局部最优解。
Dijkstra：
- 属于 贪心算法。每次选择当前距离最短的未处理顶点进行扩展，保证局部最优。
- 一旦确定了某个顶点的最短路径，Dijkstra 算法就不会再更新它，因此它更高效，但依赖于非负权重边的前提。

5. 应用场景

Bellman-Ford：
- 适用于含有负权重边的图，尤其是在需要处理负权重环的场景下（如金融市场中的套利检测、网络路由等）。
- 在负权重边比较常见或需要负权重检测的应用中更为合适。
Dijkstra：
- 适用于非负权重边的图，广泛应用于路径规划、地图导航和网络通信等场景，特别是当图中不存在负权重边时。
- 在路径规划和实际生活中的 GPS 路径导航中非常有效。

6. 算法执行方式

Bellman-Ford：
- 对所有的边进行全局松弛操作，总共执行 V-1 轮，其中 V 是顶点数。
- 每次松弛过程中，尝试更新所有边的最短路径。
Dijkstra：
- 每次选择当前未处理的最短路径顶点（通过优先队列），然后松弛其邻接边，逐步扩展出最短路径树。
- 优先选择局部最优，扩展方式逐步逼近全局最优解。

总结

特性	Bellman-Ford	Dijkstra
边权重	支持负权重边和负权重环	只能处理非负权重边
时间复杂度	O(V * E)	O((V + E) log V)
处理负权重环	能检测负权重环	无法处理负权重环
算法类型	动态规划	贪心算法
典型应用场景	负权重边的图	非负权重边的图
松弛操作	全局松弛所有边多次	逐步选择局部最短路径松弛

Bellman-Ford 算法更通用，能够处理负权重边和检测负权重环，而 Dijkstra 算法在边权重为非负时更高效。实际应用中，如果确定边权重非负且希望高效计算最短路径，通常使用 Dijkstra；如果需要处理负权重边，则使用 Bellman-Ford。

普通有向图的特性

灰色点：

图中通常会存在一个从指定起点无法到达的节点，如图中灰色的点，这些节点肯定不在路径计算的考虑范围内；

黑色轮廓白点：

代表该点从源节点可达，且可以计算出从S到该点的最短路径

红色轮廓白点：

代表该点从源节点可达，但是因为存在负权重环，不存在最短路径，因为经过负权重环无数次后，到达这样点的距离将达到负无穷
在这里插入图片描述

最短路径问题的各种可能性

Bellman-Ford算法能否处理负权重环？

不能。Bellman-Ford算法虽然能处理带有负权重的路径，但前提是路径中没有负权重环。负权重环是指环上所有边的权重之和为负数的环，并不是指环中的所有边都是负权重的。如下图所示，4到5和5到4这两条路径组成了一个环路，环路的权重为0.35+(-0.66)=-0.31，权重之和为负数，因此为负权重环。
在这里插入图片描述

命题 A。当且仅当加权有向图中至少存在一条从 s 到 v 的有向路径且所有从 s 到
v 的有向路径上的任意顶点都不存在于任何负权重环中时，s 到 v 的最短路径才是
存在的。

一个定义明确且可以解决加权有向图最短路径问题的算法要能够：

对于从起点不可达的顶点，最短路径为正无穷（+∞）；
对于从起点可达但路径上的某个顶点属于一个负权重环的顶点，最短路径为负无穷
（-∞）；
对于其他所有顶点，计算最短路径的权重（以及最短路径树）。

对于一般的有向图，我们重点解决以下问题：

负权重环的检测。给定的加权有向图中含有负权重环吗？如果有，找到它。
负权重环不可达时的单点最短路径。给定一幅加权有向图和一个起点 s 且从 s 无法到达任何负权重环，回答“是否存在一条从 s 到给定的顶点 v 的有向路径？如果有，找出最短（总权重最小）的那条路径。”等类似问题。

为什么要执行V-1轮放松？

Bellman-Ford算法需要执行V-1轮的边放松，其中每轮放松的是所有边，且没有顺序要求，这个特点也表明该算法不是一种贪婪算法。执行放松需要V-1轮的目的是为了保证最坏情况（最短路径中存在串联了所有节点的路径）下也能让路径上的所有边都被放松，如果没有放松最长路径上的所有边，则该路径则不能保证是最短的。如果图中最长的边小于V-1，则放松执行到V-1轮之前就可以完成最短路径的计算，剩下的几轮放松不会带来任何路径的缩短。下面是证明过程：

命题 B（Bellman-Ford 算法）。在任意含有 V 个顶点的加权有向图中给定起点s，从 s 无法到达任何负权重环，以下算法能够解决其中的单点最短路径问题：将distTo[s] 初始化为 0，其他 distTo[] 元素初始化为无穷大。以任意顺序放松有向图的所有边，重复 V 轮。

证明。对于从 s 可达的任意顶点 t，考虑从 s 到 t 的一条最短路径：v0 →v1→ … → vk，其中 v0 等于 s，vk 等于 t。因为负权重环是不可达的，这样的路径是存在的且 vk 不会大于V-1。我们会通过归纳法证明算法在第 i 轮之后能够得到 s 到 vi 的最短路径。最简单的情况（i=0）很容易。假设对于 i 命题成立，那么 s 到 vi 的最短路径即为 v0 → v1→ … → vi，distTo[vi] 就是这条路径的长度。现在，我们在第 i 轮中放松所有的顶点，包括 vi，因此distTo[vi+1] 不会大于 distTo[vi] 与边 vi → vi+1 的权重之和。在第 i 轮放松之后，distTo[vi+1] 必然等于 distTo[vi] 与边 vi → vi+1 的权重之和。它不可能更大，因为在第 i 轮中放松了所有顶点，包括 vi；它也不可能更小，因为它就是路径 v0 → v1→ … → vi+1 的长度，也就是最短路径了。因此，在 i+1 轮之后算法能够得到从 s 到 vi+1 的最短路径。

无负权重环的情况

放松边 0 → 2 和 0 → 4 并将顶点 2、4 加入队列。
放松边 2 → 7并将顶点 7 加入队列。放松边 4 → 5 并将顶点 5 加入队列。然
后放松失效的边 4 → 7。
放松失效的边 7 → 5、5 → 4 和 5 → 7。
放松边 7 → 3 和 5 → 1 并将顶点 3 和 1 加入队列。放松失效的边 5 → 4
和 5 → 7。
放松边 3 → 6 并将顶点 6 加入队列。放松失效的边 1 → 3。
放松失效的边 6 → 0 和 6 → 2。
放松边 6 → 4 并将顶点 4 加入队列。这条负权重边使得到顶点 4 的路径变短，
因此它的边需要被再次放松（它们在第二轮中已经被放松过）。从起点到顶点 5 和
1 的距离已经失效并会在下一轮中修正。
放松边 4 → 5 并将顶点 5 加入队列。放松失效的边 4 → 7。
放松边 5 → 1 并将顶点 1 加入队列。放松失效的边 5 → 4 和 5 → 7。
放松失效的边 1 → 3。队列为空。

在这里插入图片描述

有负权重环的情况

在这里插入图片描述

代码实现

/*******************************************************************************  Compilation:  javac BellmanFordSP.java*  Execution:    java BellmanFordSP filename.txt s*  Dependencies: EdgeWeightedDigraph.java DirectedEdge.java Queue.java*                EdgeWeightedDirectedCycle.java*  Data files:   https://algs4.cs.princeton.edu/44sp/tinyEWDn.txt*                https://algs4.cs.princeton.edu/44sp/tinyEWDnc.txt*                https://algs4.cs.princeton.edu/44sp/mediumEWD.txt*                https://algs4.cs.princeton.edu/44sp/largeEWD.txt**  Bellman-Ford shortest path algorithm. Computes the shortest path tree in*  edge-weighted digraph G from vertex s, or finds a negative cost cycle*  reachable from s.**  % java BellmanFordSP tinyEWDn.txt 0*  0 to 0 ( 0.00)*  0 to 1 ( 0.93)  0->2  0.26   2->7  0.34   7->3  0.39   3->6  0.52   6->4 -1.25   4->5  0.35   5->1  0.32*  0 to 2 ( 0.26)  0->2  0.26*  0 to 3 ( 0.99)  0->2  0.26   2->7  0.34   7->3  0.39*  0 to 4 ( 0.26)  0->2  0.26   2->7  0.34   7->3  0.39   3->6  0.52   6->4 -1.25*  0 to 5 ( 0.61)  0->2  0.26   2->7  0.34   7->3  0.39   3->6  0.52   6->4 -1.25   4->5  0.35*  0 to 6 ( 1.51)  0->2  0.26   2->7  0.34   7->3  0.39   3->6  0.52*  0 to 7 ( 0.60)  0->2  0.26   2->7  0.34**  % java BellmanFordSP tinyEWDnc.txt 0*  4->5  0.35*  5->4 -0.66********************************************************************************/import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;public class myBellmanFordSP {private double[] distTo;               // distTo[v] = distance  of shortest s->v pathprivate myDirectedEdge[] edgeTo;         // edgeTo[v] = last edge on shortest s->v pathprivate boolean[] onQueue;             // onQueue[v] = is v currently on the queue?private myLinkedQueue<Integer> queue;          // queue of vertices to relaxprivate int cost;                      // number of calls to relax()private Iterable<myDirectedEdge> cycle;  // negative cycle (or null if no such cycle)public myBellmanFordSP(myEdgeWeightedDigraph G, int s) {distTo = new double[G.V()];edgeTo = new myDirectedEdge[G.V()];onQueue = new boolean[G.V()];for (int v = 0; v < G.V(); v++)distTo[v] = Double.POSITIVE_INFINITY;distTo[s] = 0.0;// Bellman-Ford algorithmqueue = new myLinkedQueue<Integer>();queue.enqueue(s);onQueue[s] = true;while (!queue.isEmpty() && !hasNegativeCycle()) {int v = queue.dequeue();onQueue[v] = false;relax(G, v);}}// relax vertex v and put other endpoints on queue if changedprivate void relax(myEdgeWeightedDigraph G, int v) {for (myDirectedEdge e : G.adj(v)) {int w = e.to();if (distTo[w] > distTo[v] + e.weight()) {distTo[w] = distTo[v] + e.weight();edgeTo[w] = e;if (!onQueue[w]) {queue.enqueue(w);onQueue[w] = true;}}if (++cost % G.V() == 0) {findNegativeCycle();if (hasNegativeCycle()) return;  // found a negative cycle}}}public boolean hasNegativeCycle() {return cycle != null;}public Iterable<myDirectedEdge> negativeCycle() {return cycle;}// by finding a cycle in predecessor graphprivate void findNegativeCycle() {int V = edgeTo.length;myEdgeWeightedDigraph spt = new myEdgeWeightedDigraph(V);for (int v = 0; v < V; v++)if (edgeTo[v] != null)spt.addEdge(edgeTo[v]);myEdgeWeightedDirectedCycle finder = new myEdgeWeightedDirectedCycle(spt);cycle = finder.cycle();}public double distTo(int v) {if (hasNegativeCycle())throw new UnsupportedOperationException("Negative cost cycle exists");return distTo[v];}public boolean hasPathTo(int v) {return distTo[v] < Double.POSITIVE_INFINITY;}public Iterable<myDirectedEdge> pathTo(int v) {if (hasNegativeCycle())throw new UnsupportedOperationException("Negative cost cycle exists");if (!hasPathTo(v)) return null;myLinkedStack<myDirectedEdge> path = new myLinkedStack<myDirectedEdge>();for (myDirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {path.push(e);}return path;}public static void main(String[] args) {In in = new In(args[0]);int s = Integer.parseInt(args[1]);myEdgeWeightedDigraph G = new myEdgeWeightedDigraph(in);myBellmanFordSP sp = new myBellmanFordSP(G, s);// print negative cycleif (sp.hasNegativeCycle()) {for (myDirectedEdge e : sp.negativeCycle())StdOut.println(e);}// print shortest pathselse {for (int v = 0; v < G.V(); v++) {if (sp.hasPathTo(v)) {StdOut.printf("%d to %d (%5.2f)  ", s, v, sp.distTo(v));for (myDirectedEdge e : sp.pathTo(v)) {StdOut.print(e + "   ");}StdOut.println();}else {StdOut.printf("%d to %d           no path\n", s, v);}}}}
}

代码详解

这段代码实现了 Bellman-Ford 最短路径算法，用于计算加权有向图中从单一源点到所有其他顶点的最短路径。Bellman-Ford 算法具有以下特点：

它能够处理负权重边。
它能够检测图中是否存在负权重环（负环），并在发现负环时停止进一步的计算。

Bellman-Ford 算法的工作原理

Bellman-Ford 算法的核心是通过“松弛”操作不断更新最短路径估计值。它遍历所有的边，检查是否可以通过当前已知的最短路径进一步减少目标顶点的距离。如果在 V-1 轮松弛操作后（V 是顶点的数量），仍然可以更新某条边的最短路径，则图中存在负权重环。

代码结构详解

类字段

java
复制代码
private double[] distTo;               // distTo[v] = 从源点到 v 的最短路径长度
private myDirectedEdge[] edgeTo;       // edgeTo[v] = 从源点到 v 的最短路径上最后一条边
private boolean[] onQueue;             // onQueue[v] = 顶点 v 是否在队列中
private myLinkedQueue<Integer> queue;  // 用于放松的顶点队列
private int cost;                      // 松弛操作的次数
private Iterable<myDirectedEdge> cycle;  // 负权重环（如果存在）

这些变量用于存储最短路径信息、记录已经松弛过的顶点、追踪松弛操作次数，以及存储负权重环。

构造函数

java
复制代码
public myBellmanFordSP(myEdgeWeightedDigraph G, int s) {distTo  = new double[G.V()];edgeTo  = new myDirectedEdge[G.V()];onQueue = new boolean[G.V()];for (int v = 0; v < G.V(); v++)distTo[v] = Double.POSITIVE_INFINITY;distTo[s] = 0.0;// Bellman-Ford algorithmqueue = new myLinkedQueue<Integer>();queue.enqueue(s);onQueue[s] = true;while (!queue.isEmpty() && !hasNegativeCycle()) {int v = queue.dequeue();onQueue[v] = false;relax(G, v);}
}

初始化 distTo 数组，所有顶点的距离初始化为正无穷大（Double.POSITIVE_INFINITY），表示还没有路径到达这些顶点。
将源点 s 的距离设为 0.0，表示源点到自身的距离为零。
使用一个队列（queue）存储需要进行松弛操作的顶点，并从源点开始。
在松弛的过程中，不断从队列中取出顶点并进行松弛操作，直到队列为空或发现负权重环。

relax 方法

java
复制代码
private void relax(myEdgeWeightedDigraph G, int v) {for (myDirectedEdge e : G.adj(v)) {int w = e.to();if (distTo[w] > distTo[v] + e.weight()) {distTo[w] = distTo[v] + e.weight();edgeTo[w] = e;if (!onQueue[w]) {queue.enqueue(w);onQueue[w] = true;}}if (++cost % G.V() == 0) {findNegativeCycle();if (hasNegativeCycle()) return;}}
}

松弛操作：遍历与 v 相连的每条边，检查通过 v 到达 w 是否比当前 distTo[w] 更短。如果更短，则更新 distTo[w] 和 edgeTo[w]。
负权重环检测：每进行 G.V() 次松弛操作时，调用 findNegativeCycle() 来检查是否存在负权重环。

findNegativeCycle 方法

java
复制代码
private void findNegativeCycle() {int V = edgeTo.length;myEdgeWeightedDigraph spt = new myEdgeWeightedDigraph(V);for (int v = 0; v < V; v++)if (edgeTo[v] != null)spt.addEdge(edgeTo[v]);myEdgeWeightedDirectedCycle finder = new myEdgeWeightedDirectedCycle(spt);cycle = finder.cycle();
}

构造最短路径子图：根据 edgeTo 数组构造最短路径树子图 spt。
检测负权重环：使用 myEdgeWeightedDirectedCycle 类来查找子图中的负权重环。如果找到，则 cycle 保存负环的边。

路径和距离查询方法

distTo(int v)：返回从源点到顶点 v 的最短路径长度。如果存在负权重环，则抛出异常。
hasPathTo(int v)：判断是否存在从源点到顶点 v 的路径。
pathTo(int v)：返回从源点到顶点 v 的最短路径，如果存在负权重环，则抛出异常。

main 方法

java
复制代码
public static void main(String[] args) {In in = new In(args[0]);int s = Integer.parseInt(args[1]);myEdgeWeightedDigraph G = new myEdgeWeightedDigraph(in);myBellmanFordSP sp = new myBellmanFordSP(G, s);// print negative cycleif (sp.hasNegativeCycle()) {for (myDirectedEdge e : sp.negativeCycle())StdOut.println(e);}// print shortest pathselse {for (int v = 0; v < G.V(); v++) {if (sp.hasPathTo(v)) {StdOut.printf("%d to %d (%5.2f)  ", s, v, sp.distTo(v));for (myDirectedEdge e : sp.pathTo(v)) {StdOut.print(e + "   ");}StdOut.println();}else {StdOut.printf("%d to %d           no path\n", s, v);}}}
}

输入处理：从文件中读取图数据，并根据给定的源点 s 计算最短路径。
负权重环输出：如果存在负权重环，打印环中的所有边。
最短路径输出：如果不存在负权重环，打印从源点到所有其他顶点的最短路径及其权重。

总结

Bellman-Ford 算法：这段代码实现了 Bellman-Ford 算法，用于计算有向加权图中的最短路径。该算法允许处理负权重边，并能够检测负权重环。
负权重环检测：通过额外的松弛操作和 findNegativeCycle 方法，算法可以检测并输出负权重环。
优点：Bellman-Ford 算法虽然比 Dijkstra 算法慢（时间复杂度为 O(VE)），但它能处理带有负权重边的图，并且能检测负权重环。

实验数据

无负数权重环

tinyEWDn.txt

有负权重环

tinyEWDnc.txt

实验方法

当图中没有负权重环时，可以计算出从某个源节点出发到其他节点的最短路径

C:\Users\abc\IdeaProjects\myAlgorithms\src>javac myBellmanFordSP.java                  C:\Users\abc\IdeaProjects\myAlgorithms\src>java myBellmanFordSP ..\data\tinyEWDn.txt 0
0 to 0 ( 0.00)  
0 to 1 ( 0.93)  0->2 0.26000   2->7 0.34000   7->3 0.39000   3->6 0.52000   6->4 -1.25000   4->5 0.35000   5->1 0.32000
0 to 2 ( 0.26)  0->2 0.26000
0 to 3 ( 0.99)  0->2 0.26000   2->7 0.34000   7->3 0.39000
0 to 4 ( 0.26)  0->2 0.26000   2->7 0.34000   7->3 0.39000   3->6 0.52000   6->4 -1.25000
0 to 5 ( 0.61)  0->2 0.26000   2->7 0.34000   7->3 0.39000   3->6 0.52000   6->4 -1.25000   4->5 0.35000
0 to 6 ( 1.51)  0->2 0.26000   2->7 0.34000   7->3 0.39000   3->6 0.52000
0 to 7 ( 0.60)  0->2 0.26000   2->7 0.34000

当图中有负权重环时，该算法可以找到环并列出

C:\Users\abc\IdeaProjects\myAlgorithms\src>java myBellmanFordSP ..\data\tinyEWDnc.txt 0 
4->5 0.35000
5->4 -0.66000

辅助方法

myEdgeWeightedDirectedCycle

这段代码可以找到图中的环，并将环逐条边地打印出来

import edu.princeton.cs.algs4.*;public class myEdgeWeightedDirectedCycle {private myDirectedEdge[] edgeTo;private boolean[] marked;private myLinkedStack<myDirectedEdge> cycle;private boolean[] onStack;public myEdgeWeightedDirectedCycle(myEdgeWeightedDigraph G){edgeTo = new myDirectedEdge[G.V()];marked = new boolean[G.V()];onStack = new boolean[G.V()];for(int v = 0;v<G.V();v++){if(!marked[v] && cycle == null)dfs(G,v);}}private void dfs(myEdgeWeightedDigraph G, int v) {onStack[v] = true;marked[v] = true;for (myDirectedEdge e : G.adj(v)) {int w = e.to();// short circuit if directed cycle foundif (cycle != null) return;// found new vertex, so recurelse if (!marked[w]) {edgeTo[w] = e;dfs(G, w);}// trace back directed cycleelse if (onStack[w]) {cycle = new myLinkedStack<myDirectedEdge>();myDirectedEdge f = e;while (f.from() != w) {cycle.push(f);f = edgeTo[f.from()];}cycle.push(f);return;}}onStack[v] = false;}public boolean hasCycle(){ return cycle != null;}public Iterable<myDirectedEdge> cycle(){ return cycle;}public static void main(String[] args) {In in = new In(args[0]);myEdgeWeightedDigraph G = new myEdgeWeightedDigraph(in);myEdgeWeightedDirectedCycle dc = new myEdgeWeightedDirectedCycle(G);if(dc.hasCycle()){StdOut.println("Has cycle!");StdOut.print("cycle v: ");for(myDirectedEdge e:dc.cycle())StdOut.print(e + " ");}else {StdOut.println("No cycle!");}}
}

myDirectedEdge

该方法能够定义一条带权重的有向边，并且可以将边打印成v → w 权重（小数点后5位） 的格式

public class myDirectedEdge {private int v;private int w;private final double weight;public myDirectedEdge(int v, int w, double weight){this.v = v;this.w = w;this.weight = weight;}public double weight(){ return weight; }public int from(){ return v; }public int to(){ return w; }public String toString(){ return String.format("%d -> %d %.5f",v,w,weight); }
}

myEdgeWeightedDigraph

该方法能够构建一个带权重的有向图

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;public class myEdgeWeightedDigraph {private myBag<myDirectedEdge>[] adj;private int V;private int E;private static final String NEWLINE = System.getProperty("line.separator");public myEdgeWeightedDigraph(int V){this.V = V;this.E = 0;adj = (myBag<myDirectedEdge>[]) new myBag[V];for(int v=0;v<V;v++)adj[v] = new myBag<myDirectedEdge>();}public myEdgeWeightedDigraph(In in){this(in.readInt());int E = in.readInt();for(int i = 0; i<E; i++){int v = in.readInt();int w = in.readInt();double weight = in.readDouble();myDirectedEdge e = new myDirectedEdge(v,w,weight);addEdge(e);}}public void addEdge(myDirectedEdge e){adj[e.from()].add(e);E++;}public int V() {return V;}public int E() {return E;}public Iterable<myDirectedEdge> adj(int v) { return adj[v]; }public Iterable<myDirectedEdge> edges(){myBag<myDirectedEdge> bag = new myBag<myDirectedEdge>();for(int v = 0;v<V;v++)for(myDirectedEdge e:adj[v])bag.add(e);return bag;}public String toString() {StringBuilder s = new StringBuilder();s.append(V + " vertexes " + E + " edges " + NEWLINE);for (int v = 0; v < V; v++) {s.append(v + ": ");for (myDirectedEdge e : adj[v]) {s.append(e + "  ");}s.append(NEWLINE);}return s.toString();}public static void main(String[] args){In in = new In(args[0]);myEdgeWeightedDigraph G = new myEdgeWeightedDigraph(in);StdOut.println(G);}
}