Digstra 算法 Java

Question

代表vertex

public interface Vertex<V> {
    public V element()throws InvalidVertexException;
}

代表edge

public interface Edge<E,V> {
    public E element()throws InvalidEdgeException;
    public Vertex<V>[] vertices();
}

代表Graph<V,E>

public interface Graph<V, E> {
    public Iterable<Vertex<V>> vertices();
    public Iterable<Edge<E, V>> incidentEdges(Vertex<V> v)
    public Vertex<V> opposite(Vertex<V> v, Edge<E, V> e);
    public Iterable<Edge<E, V>> edges();
    public Vertex<V> insertVertex(V o);
    public Edge<E, V> insertEdge(Vertex<V> u, Vertex<V> v, E o);
    public Edge<E, V> insertEdge(V elem1, V elem2, E o);
}

class Dijkstra 实现算法

public class Dijkstra<V, E> {

    //To store a distance from each of the vertices to the vertex source.
    private Map<Vertex<V>, Integer> distances;
    //To save the predecessor vertex on the shortest path
    private Map<Vertex<V>, Vertex<V>> path;
    //To save visited vertices
    private Set<Vertex<V>> visited;

    //Construtor
    public Dijkstra() {
        this.distances = new HashMap<>();
        this.path = new HashMap<>();
        this.visited = new HashSet<>();
    }

    //remove u from Q;
    private Vertex<V> remove(ArrayList<Vertex<V>> queue) {//Q = Q - {v}
        Iterator<Vertex<V>> it = queue.iterator();
        while (it.hasNext()) {
            Vertex<V> u = it.next();
            if (u != null) {
                it.remove();
                return u;
            }
        }
        return null;
    }

算法实现

//Dijkstra (graph, origin)
private void dijkstra(Graph <V,E> graph, Vertex<V> origin) {
  //Q list of vertex
  ArrayList <Vertex<V>> Q = new ArrayList<> ();
  //for each vertex v in the graph
  for (Vertex <V> v: graph.vertices()) {
    //vertex v diferent vertex origin
    if (v.element().equals(origin.element()) != true) {
      //distance [v] = Infinite;
      distances.put(v, Integer.MAX_VALUE);
      //predecessor [v] = -1;
      path.put(origin, v);
    } //vertex v equal vertex origin
    else {
      //distance [source] = 0;
      distances.put(origin, Integer.MIN_VALUE);
    } //Q = all vertices of graph;
    Q.add(v);
  }

  //while (Q is not empty) do,
  while (Q.isEmpty() != true) {
    //remove u from Q;
    Vertex <V> u = remove(Q);
    //u = vertex is graph with less distance;
    int distanceU = distances.get(u);
    //if (distance [u] == Infinity)
    if (distanceU == Integer.MAX_VALUE) {
      //return visited;
      visited.add(u);
    } else {

      for (Edge <E, V> edge: graph.incidentEdges(u)) {
        //for every neighbor v of u
        Vertex <V> v = graph.opposite(u, edge);
        //distance [v]
        int distanceV = distances.get(v);
        //distance between u and v;
        int distanceUV = distanceU + distanceV;
        //d = distance [u] + distance between u and v;
        int d = distanceU + distanceUV;
        //(d < distance [v])
        if (d < distances.get(v)) {
          //distance [v] = d;
          distances.put(v, d);
          //predecessor [v] = u;
          path.put(u, v);
        }
      }
    }
  }
}

这个图包含 4 个顶点和边，如果我计算 [C, D]

之间的最小距离

结果应该是 [C,D] = [C,A] -> [A, D]

计算顶点原点到终点的距离的方法

I could not find the correct logic to implement to get the correct result, I followed the description of the dijkstra algorithm but I can not find any solution to solve

public void executeDijkstra(Graph<V, E> graph, Vertex<V> origin, Vertex<V> destiny) {
     //execute dijkstra
     dijkstra(graph, origin);
    //need to return all vertices with distances   
}

有什么建议吗？

Answer 1

您的代码充满错误。

remove 方法应该从 Q 中删除距离最小的顶点：

private Vertex<V> remove(List<Vertex<V>> queue) {//Q = Q - {v}
    if (queue.isEmpty()) {
        return null;
    }
    int ix = 0;
    int min = distances.get(queue.get(0));
    for (int i = 1; i < queue.size(); ++i) {
        int dist = distances.get(queue.get(i));
        if (dist < min) {
            ix = i;
            min = dist;
        }
    }
    return queue.remove(ix);
}

初始化：不初始化路径，将到原点的距离初始化为零（如注释）：

    for (Vertex<V> v : graph.vertices()) {
        //vertex v diferent vertex origin
        if (v.element().equals(origin.element()) != true) {
            //distance [v] = Infinite;
            distances.put(v, Integer.MAX_VALUE);
        } //Q = all vertices of graph;
        Q.add(v);
    }
    //distance [source] = 0;
    distances.put(origin, 0);

现在，您的图表似乎未加权，否则，它将是 Graph<V,Integer>，因此我假设任何边的距离为 1:

    //while (Q is not empty) do,
    while (!Q.isEmpty()) {
        //remove u from Q;
        Vertex<V> u = remove(Q);
        //u = vertex is graph with less distance;
        int distanceU = distances.get(u);
        //if (distance [u] == Infinity)
        for (Edge<E, V> edge : graph.incidentEdges(u)) {
            //for every neighbor v of u
            Vertex<V> v = graph.opposite(u, edge);
            //distance [v]
            int d = distanceU + 1;
            //(d < distance [v])
            if (d < distances.get(v)) {
                //distance [v] = d;
                distances.put(v, d);
                //predecessor [v] = u;
                path.put(v, u);
            }
        }
    }

现在在您的示例中构建图形：

        Graph<String,String> graph = new GraphImpl<>();
        Vertex<String> a = graph.insertVertex("a");
        Vertex<String> b = graph.insertVertex("b");
        Vertex<String> c = graph.insertVertex("c");
        Vertex<String> d = graph.insertVertex("d");
        graph.insertEdge(a, b, "ab");
        graph.insertEdge(a, c, "ac");
        graph.insertEdge(a, d, "ad");

调用dijkstra(graph, c)后，你得到：

dijkstra.path:

b-a
a-c
d-a

dijkstra.distances:

b: 2
a: 1
c: 0
d: 2

小菜一碟！

Digstra 算法 Java

Algorithm Dijkstra Java

java

algorithm

dijkstra