Get additional information from an edge after a graph search using Djikstra algorithm

Question

I'm using this implementation to perform a graph search. The search is working. The shortest path is returned by this function:

public static List<Vertex> getShortestPathTo(Vertex target)
{
    List<Vertex> path = new ArrayList<Vertex>();

    for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
        path.add(vertex);

    Collections.reverse(path);
    return path;
}

However, I added a few properties to the edges, and I need that information extracted to.

How do I find out which edge has been used for the path?

Answer 1

If you are sure, your graph doesn't contain multiple edges with the same source and targetnode, you can reconstruct the edges from the adjacencies and previous field of class Vertex.

Something like the following should collect all edges in a List (not tested).

List<Edge> edge_path = new ArrayList<Edge>();
for (int i = 1; i < path.size(); i++) {
    Vertex v = path.get(i);

    for (Edge e: v.previous.adjacencies)
        if (e.target == v) {
            edge_path.add(e);
            break;
        }

However if your graph contains multi edges, you have to adapt the path finding algorithm itself.