<分区>
我想知道是否有人可以给出一个对以下代码不起作用的反例(负权重的有向图)(Dijkstra 算法与二叉堆)。我已经尝试了几个例子，但似乎在负边上工作正常，只要我们有更好的方式到达某个节点，它就会更新所有相邻节点的距离。下面是例子
(0) ----2----> (3) -----1-----> (4)
| ^
4 |
| -9
v |
(1) ----6----> (2)
it will print out => 0, 4, 10, 1, 2
还有
(0) ---1---> (1) ---1---> (2)
| ^
| |
100 -5000
| |
\---------> (3) ----------/
this will print => 0, 1, -4900, 100
下面是Java中的代码
public static void dijkstra(DirectedGraph G, int source) {
int[] distTo = new int[G.V()];
Arrays.fill(distTo, Integer.MAX_VALUE);
distTo[source] = 0;
PriorityQueue<Node> pq = new PriorityQueue<Node>();
pq.add(new Node(source, 0));
while (!pq.isEmpty()) {
Vertex vertex = pq.poll();
for (WeightedEdge edge : G.adjTo(vertex.node)) {
if (edge.weight + distTo[edge.from] < distTo[edge.to]) {
distTo[edge.to] = distTo[edge.from] + edge.weight;
Vertex adjNode = new Vertex(edge.to, distTo[edge.to]);
if (pq.contains(adjNode))
pq.remove(adjNode);
pq.add(adjNode);
}
}
}
for (int dist : distTo)
System.out.print(dist + " ");
}
static class Vertex implements Comparable<Vertex> {
int node;
int weight;
public Vertex(int node, int weight){
this.node = node;
this.weight = weight;
}
@Override
public int compareTo(Vertex other) {
return weight - other.weight;
}
}
public class DirectedGraph {
private final int V;
private int[][] G;
public int V() {
return V;
}
public DirectedGraph(int V) {
this.V = V;
G = new int[V][V];
}
public void addEdge(int v, int w, int weight) {
G[v][w] = weight;
}
public List<WeightedEdge> adjTo(int v) {
List<WeightedEdge> edges = new LinkedList<WeightedEdge>();
for (int i = 0; i < V; i++)
if (G[v][i] != 0)
edges.add(new Edge(v, i, G[v][i]));
return edges;
}
}