Anonymous user
Talk:Dijkstra's algorithm: Difference between revisions
→Replaced 'pushleft' with 'appendleft' in the Python snippet
| (11 intermediate revisions by 6 users not shown) | |||
Line 16:
I think there may be a bug: The java one uses a TreeSet to maintain the unvisited set - but it is doing equality comparisons with compareTo, which is looking at the distance and not the identity of the node. So if two distinct nodes happen to have the same dist value at the same time, then either one could get removed from the unvisited set.
There are several bugs in the Java realization of this algorithm
For example for the Graph
private static final Graph.Edge[] GRAPH = {
new Graph.Edge("17", "1", 20),
new Graph.Edge("1", "17", 20),
new Graph.Edge("1", "7", 2),
new Graph.Edge("7", "14", 15),
new Graph.Edge("1", "3", 5),
new Graph.Edge("3", "14", 2),
new Graph.Edge("1 ", "2", 5),
};
private static final String START = "17";
private static final String END = "14";
The path from the vertex "17" to "14" will be
17 -> 1 -> 7 -> 14 with summary distance 37
while it must me
17 -> 1 -> 3 -> 14 with summary distance 27
please see the fixed version of this algorithm below
package graph;
/**
* @author Archil Matchavariani
*/
import java.util.*;
public class Dijkstra {
// private static final Graph.Edge[] GRAPH = {
// new Graph.Edge("a", "b", 7),
// new Graph.Edge("a", "c", 9),
// new Graph.Edge("a", "f", 14),
// new Graph.Edge("b", "c", 10),
// new Graph.Edge("b", "d", 15),
// new Graph.Edge("c", "d", 11),
// new Graph.Edge("c", "f", 2),
// new Graph.Edge("d", "e", 6),
// new Graph.Edge("e", "f", 9),
// };
// private static final String START = "a";
// private static final String END = "e";
private static final Graph.Edge[] GRAPH = {
new Graph.Edge("17", "1", 20),
new Graph.Edge("1", "17", 20),
new Graph.Edge("1", "7", 2),
new Graph.Edge("7", "14", 15),
new Graph.Edge("1", "3", 5),
new Graph.Edge("3", "14", 2),
new Graph.Edge("1 ", "2", 5),
new Graph.Edge("1 ", "6", 5),
};
private static final String START = "17";
private static final String END = "14";
public static void main(String[] args) {
Graph g = new Graph(GRAPH);
g.dijkstra(START);
g.printPath(END);
//g.printAllPaths();
}
}
class Graph {
private final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges
/**
* One edge of the graph (only used by Graph constructor)
*/
public static class Edge {
public final String v1, v2;
public final int dist;
public Edge(String v1, String v2, int dist) {
this.v1 = v1.trim();
this.v2 = v2.trim();
this.dist = dist;
}
}
/**
* One vertex of the graph, complete with mappings to neighbouring vertices
*/
public static class Vertex implements Comparable<Vertex> {
public final String name;
public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
public Vertex previous = null;
public final Map<Vertex, Integer> neighbours = new HashMap<>();
public Vertex(String name) {
this.name = name;
}
private void printPath() {
if (this == this.previous) {
System.out.printf("%s", this.name);
} else if (this.previous == null) {
System.out.printf("%s(unreached)", this.name);
} else {
this.previous.printPath();
System.out.printf(" -> %s(%d)", this.name, this.dist);
}
}
public int compareTo(Vertex other) {
return Integer.compare(dist, other.dist);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Vertex vertex = (Vertex) o;
return name != null ? name.equals(vertex.name) : vertex.name == null;
}
@Override
public int hashCode() {
return name != null ? name.hashCode() : 0;
}
}
/**
* Builds a graph from a set of edges
*/
public Graph(Edge[] edges) {
graph = new HashMap<>(edges.length);
//one pass to find all vertices
for (Edge e : edges) {
if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1));
if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2));
}
//another pass to set neighbouring vertices
for (Edge e : edges) {
graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
//graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph
}
}
/**
* Runs dijkstra using a specified source vertex
*/
public void dijkstra(String startName) {
if (!graph.containsKey(startName)) {
System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName);
return;
}
final Vertex source = graph.get(startName);
PriorityQueue<Vertex> q = new PriorityQueue<>();
source.dist = 0;
source.previous = source;
q.add(source);
dijkstra(q);
}
/**
* Implementation of dijkstra's algorithm using a binary heap.
*/
private void dijkstra(final PriorityQueue<Vertex> q) {
Vertex u, v;
while (!q.isEmpty()) {
u = q.poll(); // vertex with shortest distance (first iteration will return source)
if (u.dist == Integer.MAX_VALUE) break; // we can ignore u (and any other remaining vertices) since they are unreachable
//look at distances to each neighbour
for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
v = a.getKey(); //the neighbour in this iteration
final int alternateDist = u.dist + a.getValue();
if (alternateDist < v.dist) { // shorter path to neighbour found
q.remove(v);
v.dist = alternateDist;
v.previous = u;
q.add(v);
}
}
}
}
/**
* Prints a path from the source to the specified vertex
*/
public void printPath(String endName) {
if (!graph.containsKey(endName)) {
System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName);
return;
}
graph.get(endName).printPath();
System.out.println();
}
/**
* Prints the path from the source to every vertex (output order is not guaranteed)
*/
public void printAllPaths() {
for (Vertex v : graph.values()) {
v.printPath();
System.out.println();
}
}
}
the code quality is not the best but the functionality is correct now
== Floyd–Warshall ==
Line 32 ⟶ 261:
: The Go code is fine for what it's doing, but it's best not to draw conclusions about the performance based only on the current test case. --[[User:Ledrug|Ledrug]] 06:55, 10 December 2011 (UTC)
:: All very good points. Constructing the edge list took 133ms, constructing the linked representation took 225ms, and then the path search took only 7ms. It does seem likely that the graph wouldn't be fully connected. Spoon, thanks for the simplifications to the Go code! —[[User:Sonia|Sonia]] 00:20, 11 December 2011 (UTC)
== Bug in C implementation ==
The line:
int i = h->index[v] || ++h->len;
Does not evaluate correctly the expression. If h->index[v] == 0 then ++h->len is not assigned to i, instead 1 is assigned. In theory the compiler should assign the right side expression to i but is not working with gcc. For example, the graph:
add_edge(g, 'a', 'b', 1);
add_edge(g, 'b', 'c', 1);
add_edge(g, 'c', 'd', 1);
add_edge(g, 'd', 'e', 1);
add_edge(g, 'e', 'f', 1);
add_edge(g, 'f', 'a', 1);
add_edge(g, 'a', 'g', 2);
add_edge(g, 'g', 'b', 2);
add_edge(g, 'c', 'g', 2);
add_edge(g, 'g', 'd', 2);
add_edge(g, 'e', 'g', 2);
add_edge(g, 'f', 'g', 2);
dijkstra(g, 'a', 'e');
print_path(g, 'e');
Will output '5 agde' and is wrong because path '4 abcde' is shorter. Next line fixes the problem:
int i = h->index[v] ? h->index[v] : ++h->len;
== Directed vs undirected graphs ==
Line 51 ⟶ 306:
Ahhhh see directed vs. undirected above.
Sorry --[[User:Walterpachl|Walterpachl]] 08:55, 21 December 2012 (UTC)
== Replaced 'pushleft' with 'appendleft' in the Python snippet ==
Must specify explicitly that the python snippet solution should be at least in python 2.7 due to the dictionary comprehension feature used. And also, must replace the 'pushleft' with 'appendleft'.
Updated 'queue' to 'deque' and re-updated 'pushleft' to 'appendleft' and tested running in python 2.7 and python 3.5 on 1/19/2017
== Javascript version ==
var roads = [
{from: 0, to: 1, drivingTime: 5},
{from: 0, to: 2, drivingTime: 10},
{from: 1, to: 2, drivingTime: 10},
{from: 1, to: 3, drivingTime: 2},
{from: 2, to: 3, drivingTime: 2},
{from: 2, to: 4, drivingTime: 5},
{from: 3, to: 2, drivingTime: 2},
{from: 3, to: 4, drivingTime: 10}
];
function navigate(roads, start, finish) {
var vert = [],Q;
var neighb = {}, dist = {},prev = {};
for(var edge of roads){
vert.indexOf(edge.from) === -1 && vert.push(edge.from);
vert.indexOf(edge.to) === -1 && vert.push(edge.to);
if(!neighb[edge.from]) neighb[edge.from] = [];
neighb[edge.from].push({end : edge.to,cost : edge.drivingTime});
}
vert.forEach((val) => {dist[val] = Infinity;prev[val] = null});
dist[start] = 0;
Q = vert;
while(Q.length > 0){
var min = Infinity;
var u;
Q.forEach((val) => {
if(dist[val] < min){
min = dist[val];
u = val;
}
});
Q = Q.slice(0,Q.indexOf(u)).concat(Q.slice(Q.indexOf(u) + 1,Q.length));
if(dist[u] == Infinity || u == finish) break;
if(neighb[u]){
neighb[u].forEach((val) => {
var alt = dist[u] + val.cost;
if(alt < dist[val.end]){
dist[val.end] = alt;
prev[val.end] = u;
}
});
}
}
var path = [];
u = finish;
while(prev[u] !== undefined){
path.unshift(u);
u = prev[u];
}
return path.length > 0 ? path : null;
}
== Perl version faulty ==
The push_priority() function of the perl implementation is faulty. This can most clearly be seen by adding an edge from 'b' to 'e' of weight 1 making s-b-e the shortest path. Yet this new path is not picked up. The vertices appears to be dequeued from the function in their inserted order, rather than by priority. In the function the binary search comparison appears to be comparing hash addresses.
:Fixed. [[User:Trizen|Trizen]] ([[User talk:Trizen|talk]])
| |||