1
$\begingroup$

I'm learning about single source shortest path algorithms and need to clarify few doubts-

  1. Does Dijkstra’s assumes that the weights of edges in a graph searched by it are positive integers.
  2. Does Dijkstra’s assumes that the graph searched by it is free of cycles.
  3. Relaxing an edge is same as setting its weight to 0.
  4. Does Dijkstra’s yields only costs of shortest paths, requiring lot of extra computation to find the intermediate vertices on shortest paths.
  5. Dijkstra's useful only when edge weights are geographical distances along paths traversed on ground or water.
$\endgroup$
1
$\begingroup$
  1. Does Dijkstra’s assumes that the weights of edges in a graph searched by it are positive integers?

Dijkstra’s shortest path algorithm works for non-negative numbers. The Bellman-Ford algorithm works in the general case, i.e. works for the negative numbers, too.

  1. Does Dijkstra’s assumes that the graph searched by it is free of cycles.

In an undirected graph, If there is no cycle, it is a Tree, not necessarily rooted. The paths are unique. Dijkstra’s algorithm can work with cycles.

You probably mean that free of negative cycles; If there is a negative cycle and the source can reach it, then the cost of path has not defined.

  1. Relaxing an edge is same as setting its weight to 0.

Relaxation is historical naming, the correct name is tighten. Relaxation tests an edge wheater in can improve the current estimate of a node.

  1. Does Dijkstra’s yields only costs of shortest paths, requiring lot of extra computation to find the intermediate vertices on shortest paths.

Actually, it yields the shortest paths tree with their values, the running time is $\mathcal{O}((V+E)\log V).$ If you look at the algorithm, it considers only the current neighbors while constructing the shortest path tree. The bottleneck is the extract-min operation on the Heap. For a theoretical speed up, one can use Fibonacci Heaps that yield $\mathcal{O}(V \log V + E)$

During the relaxation process, the predecessors updated only if there is a need for relaxation. When the Dijkstra's algorithm finishes, the shortest path tree is ready.

  1. Dijkstra's useful only when edge weights are geographical distances along paths traversed on ground or water.

Remember, Dijkstra's algorithm can find one-to-all shortest path if the Graph is weighted and directed. It doesn't care where the map is taken as long as it is modeled as a Graph. However, if the graph is an actual map and/or there is also a heuristic distance information one can achieve better than Dijkstra's algorithm, see A* and this comparison article Engineering Route Planning Algorithms.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.