Questions tagged [dijkstra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
84 views

Some questions about shortest-path algorithms

I'm trying to understand why anyone would prefer Floyd-Warshal over Dijkstra: Dijkstra gives a correct result, using an understandable system, combined with backtracking. Floyd-Warshal makes an ...
Dominique's user avatar
  • 1,910
11 votes
7 answers
3k views

Did Dijkstra intend for code modularization, when he wrote about separation of concerns?

First, I read an excerpt Edsger W. Dijkstra's 1974 paper "On the role of scientific thought": Let me try to explain to you, what to my taste is characteristic for all intelligent thinking. It is, ...
Dennis's user avatar
  • 8,217
6 votes
1 answer
1k views

Mixing heuristic functions in A*

I have applied a custom heuristic to my A* search. It is admissible, but it is not consistent (monotonic). As such, I am not guaranteed to find the shortest path. I had assumed I could use a hybrid ...
Synesso's user avatar
  • 574
1 vote
1 answer
192 views

Is my understanding of dijkstra and plain Breadth-First Search correct?

I need to help to validate whether my understanding of when to use Dijkstra and when BFS are correct. My way of understanding BFS and Dijkstra, when to use what, am I correct? As I see it. Being ...
Jan Glaser's user avatar
1 vote
1 answer
1k views

Find fastest connection to a certain point

What i'm trying to implement is a program that is searching for the fastest connection from one station to other at a given time of the day. I have a number of stations n, and a number m of lines ...
Ion's user avatar
  • 111
2 votes
3 answers
14k views

Algorithm to determine the fastest route passing in all points

Given a starting point A and an end point E, I need an algorithm to determine the minimum transit route in a city that passes through all points (A, B, C, D, E) and is the fastest possible. I know I ...
Vinicius's user avatar
  • 129
1 vote
3 answers
94 views

Dijkstra function for navigation for disadvantaged

Is there a way we can write a function for Dijkstra to determine which node to enqueue and which to discard. This is for a navigation solution for people with disabilities where path to stairs may be ...
Jason6916's user avatar
  • 113
1 vote
2 answers
2k views

Why does this implementation of Dijkstra's algorithm work in O(n^2)?

Here is the code I use for implementing Dijkstra's algorithm. Consider a graph with n vertices and m edges. Shouldn't it run in O(n^2 m) ? Someone may say that there are n vertices and each edge gets ...
Dhruv Mullick's user avatar
4 votes
1 answer
2k views

Shortest Path Between Two Nodes in a +10 Million Nodes Graph

I have my own knowledge graph representation, read from ConceptNet and NELL, containing tens of millions of nodes in which I want to calculate the nearest distance (if any) between two concept nodes. ...
Nordlöw's user avatar
  • 151
13 votes
1 answer
8k views

Am I right about the differences between Floyd-Warshall, Dijkstra's and Bellman-Ford algorithms?

I've been studying the three and I'm stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you. Dijkstra's algorithm is used only when ...
Programming Noob's user avatar
17 votes
5 answers
12k views

Algorithm to determine fastest route?

Let's say we're going from 1 to 5. The shortest route will be 1-4-3-5 (total: 60 km). We can use Dijkstra's algorithm to do that. Now the problem is, the shortest route is not always the fastest one,...
anta40's user avatar
  • 281