David Gleich

My apologies, I had a few typos in the citation that made it difficult to find. I've fixed this issue. The doi is http://dx.doi.org/10.1145/278298.278303

As it seems, there's also a built function for my problem, path_from_pred.m...

And a next question as well:

I have a graph that represents e.g. cities and the arcs are distances between them. Is there a way to have some kind of maximum length as an constraint to the shortest path problem?

"How can I get the shortest path between nodes s and t? What I'm looking for is list of nodes, not just the distance..."

Use the predecessors returned by the shortest_paths function.
For example:

load graphs/clr-25-2.mat
startnode = 1;
endnode = 5;
[d pred] = shortest_paths(A,startnode);

cur = endnode;
path = [];
while(true)
    path = [cur path];
    if cur == startnode
        break;
    end
    cur = pred(cur);
end

In this example, path = [1 3 5], which represents the shortest path from node 1 to node 5.

Never mind my previous question. How can I get the shortest path between nodes s and t? What I'm looking for is list of nodes, not just the distance...