Software Engineering Stack Exchange
Software Engineering Stack Exchange

Questions tagged [dijkstra]

11 questions
17
votes
5 answers

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, because of traffic jams or other factors. For…
anta40
  • 281
  • 1
  • 2
  • 6
13
votes
1 answer

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 you have a single source and you want to know…
Programming Noob
  • 473
  • 4
  • 7
10
votes
7 answers

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, that one is willing to study in depth an aspect of…
Dennis
  • 8,157
  • 5
  • 36
  • 68
6
votes
1 answer

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 approach that calculates both the euclidian…
Synesso
  • 574
  • 4
  • 11
4
votes
1 answer

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. The application is to find out how two concepts…
Nordlöw
  • 151
  • 5
2
votes
3 answers

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 can represent this problem in a graph, but I'm not…
Vinicius
  • 129
  • 1
  • 1
  • 2
1
vote
1 answer

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 entire list and filters in there. The only thing I…
Dominique
  • 1,705
  • 2
  • 14
  • 24
1
vote
1 answer

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 given a graph, that can be imagined as N-ary tree,…
Jan Glaser
  • 113
  • 3
1
vote
1 answer

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 that connect this stations. Each line has…
Ion
  • 111
  • 5
1
vote
3 answers

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 shorter but not preferable to wheelchair bound…
Jason6916
  • 113
  • 3
1
vote
2 answers

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 processed once, therefore it is O(n m). But the…
Dhruv Mullick
  • 167
  • 8