dijkstra

Dijkstra Shortest Path with VertexList = ListS in boost graph

by

BGL actually has an example of using dijkstra_shortest_paths with listS/listS, but it’s not linked to from the HTML documentation: http://www.boost.org/doc/libs/release/libs/graph/example/dijkstra-example-listS.cpp What the error message is trying to tell you (error: no match for ‘operator=’ in ‘index.boost::adj_list_vertex_property_map…ValueType = boost::detail::error_property_not_found…) is that there is no per-vertex storage for the vertex_index_t property, which is what adj_list_vertex_property_map needs. To … Read more

graph – Dijkstra for The Single-Source Longest Path

by

No, we cannot1 – or at the very least, no polynomial reduction/modification is known – longest path problem is NP-Hard, while dijkstra runs in polynomial time! If we can find a modfication to dijsktra to answer longest-path problem in polynomial time, we can derive P=NP If not, then provide a counterexample. This is very bad … Read more

Find cycle of shortest length in a directed graph with positive weights

by

You can easily modify Floyd-Warshall algorithm. (If you’re not familiar with graph theory at all, I suggest checking it out, e.g. getting a copy of Introduction to Algorithms). Traditionally, you start path[i][i] = 0 for each i. But you can instead start from path[i][i] = INFINITY. It won’t affect algorithm itself, as those zeroes weren’t … Read more

Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?

by

Dijkstra allows assigning distances other than 1 for each step. For example, in routing the distances (or weights) could be assigned by speed, cost, preference, etc. The algorithm then gives you the shortest path from your source to every node in the traversed graph. Meanwhile BFS basically just expands the search by one “step” (link, … Read more

Find the shortest path in a graph which visits certain nodes

by

Everyone else comparing this to the Travelling Salesman Problem probably hasn’t read your question carefully. In TSP, the objective is to find the shortest cycle that visits all the vertices (a Hamiltonian cycle) — it corresponds to having every node labelled ‘mustpass’. In your case, given that you have only about a dozen labelled ‘mustpass’, … Read more

Why doesn’t Dijkstra’s algorithm work for negative weight edges?

by

Recall that in Dijkstra’s algorithm, once a vertex is marked as “closed” (and out of the open set) – the algorithm found the shortest path to it, and will never have to develop this node again – it assumes the path developed to this path is the shortest. But with negative weights – it might … Read more