This is probably a bit OT, as I'm not looking for a c++ implementaiton of
Dijkstra's algorithm, rather I'm just trying to understand it (is there a
better place then here to ask this question?). I've reviewed several sites
and the faq (no, I'm not asking you to do my homework for me) and the
examples don't give me the information I need to continue on. I'm working
with a complex tree, and am not sure how to logically apply Dijkstra's
algorithm to it. This is how I understand it in my own words:
Let's say I start at A, and the adjacent vertex with the least weight is
AB, and the weight of the edge is 5.
A5 B
From here, there are only 3 places I can go as follows:
A6C
A5B2D
A5B3E
From AC is 6, from ABD is 7, from ABE is 8. The next shortest path is
from AC for a total of 6, not ABD or ABE.
D for a total of 7 or 8. Here is where I'm confused: does my second step
have to be a continuation of the first step, IOW can I only go from B to the
next unused vertex, or should I select the next unused vertex adjacent to a
used vertex that gives me the leasted cumulative weight? If the latter, then
I should choose AC for 6, then ABD for 7, and lastly ABE for 8. At each
stop, I look at all adjacent nodes and fill in the lessor of the already
figured distance to the node, and the distance from the node I stopped at to
that node. If I do this, I eventually get what I believe is the shortest
path to my destination, but I'm not sure I did it right. 3 4974
Ook wrote: This is probably a bit OT, as I'm not looking for a c++ implementaiton of Dijkstra's algorithm, rather I'm just trying to understand it (is there a better place then here to ask this question?).
comp.programming comes to mind as one option
I've reviewed several sites and the faq (no, I'm not asking you to do my homework for me) and the examples don't give me the information I need to continue on. I'm working with a complex tree, and am not sure how to logically apply Dijkstra's algorithm to it. This is how I understand it in my own words:
Let's say I start at A, and the adjacent vertex with the least weight is AB, and the weight of the edge is 5.
A5 B
From here, there are only 3 places I can go as follows:
A6C A5B2D A5B3E
From AC is 6, from ABD is 7, from ABE is 8. The next shortest path is from AC for a total of 6, not ABD or ABE. D for a total of 7 or 8. Here is where I'm confused: does my second step have to be a continuation of the first step, IOW can I only go from B to the next unused vertex,
no
or should I select the next unused vertex adjacent to a used vertex that gives me the leasted cumulative weight?
yes
If the latter, then I should choose AC for 6, then ABD for 7, and lastly ABE for 8.
Certaintly choose AC for 6. Then you update the distances based on
having made that choice and choose the next closest item (which may be
ABD for 7 or may be something else which becomes closer by virtue of
the path through C).
At each stop, I look at all adjacent nodes and fill in the lessor of the already figured distance to the node, and the distance from the node I stopped at to that node. If I do this, I eventually get what I believe is the shortest path to my destination, but I'm not sure I did it right.
That is the basic idea of the algorithm. (But bear in mind that it
doesn't work if any edge has negative length.) comp.programming comes to mind as one option
Thanks, I'll try there :)
or should I select the next unused vertex adjacent to a used vertex that gives me the leasted cumulative weight?
yes
That is what I was missing. Most of the explanations I've seen seem to
assume you already know how it works, and don't clearly explain it. :P
Matthew L Reed wrote: comp.programming comes to mind as one option
Thanks, I'll try there :)
or should I select the next unused vertex adjacent to a
used vertex that gives me the leasted cumulative weight?
yes
That is what I was missing. Most of the explanations I've seen seem to assume you already know how it works, and don't clearly explain it. :P
I'd say find a better explanation, as there are good ones out there.
"Introduciton to Algorithms" by Cormen et al. is one example. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Herman 
last post by:
Hi everyone, I'm implementing Dijkstra's algorithm for a class
project, and I'm having trouble compiling the class that runs the
algorithm. All of the other files compile fine except for this one....

by: ThanhVu Nguyen 
last post by:
Hi all,
I need recommendation for a very fast shortest path algorithm. The
edges are all directed, positive weights. Dijkstra shortest path will
solve it just fine but the if the graph is not...

by: A_StClaire_ 
last post by:
implemented Dijkstra's algorithm as follows. plz pour on the negative
criticism cuz I know I have a ton to learn.
oh, before you flame me regarding the language, my class was told to do
this in...

by: A_StClaire_ 
last post by:
thoughts or criticism anyone?
using System;
namespace Dijkstra
{
public class Algorithm
{
private const int nodes = 10;

by: arlef 
last post by:
Can somebody please explain and provide pseudocode for the Dijkstra
algorithm?
I'm trying to implement the Dijkstra shortest path algorithm. However, I'm
finding it extremely difficult to...

by: Josh Zenker 
last post by:
I've been working on an implementation of Dijkstra's algorithm on and
off for the past few days. I thought I was close to being finished,
but clearly I've done something wrong. I'm not a very...

by: abhradwip 
last post by:
I want to write a program which will find the shortest path between n no. of cities using dijkstra's algorithm ...... but could not do it..... i have written a program which will give the shortest...

by: shashankbs 
last post by:
Given a topology and a certain node X, find the shortest path tree
with X as the root.
* Input: a topology file similar to the following (which is a threenode
ring)
...

by: Glenton 
last post by:
Hi All
Here is a very simple little class for finding a shortest route on a network, following Dijkstra's Algorithm:
#!/usr/bin/env python
#This is meant to solve a maze with Dijkstra's...

by: lllomh 
last post by:
Define the method first
this.state = {
buttonBackgroundColor: 'green',
isBlinking: false, // A new status is added to identify whether the button is blinking or not
}
autoStart=()=>{

by: DJRhino 
last post by:
Was curious if anyone else was having this same issue or not....
I was just Up/Down graded to windows 11 and now my access combo boxes are not acting right. With win 10 I could start typing...

by: isladogs 
last post by:
The next Access Europe meeting will be on Wednesday 4 Oct 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM)
The start time is equivalent to 19:00 (7PM) in Central...

by: Aliciasmith 
last post by:
In an age dominated by smartphones, having a mobile app for your business is no longer an option; it's a necessity. Whether you're a startup or an established enterprise, finding the right mobile app...

by: giovanniandrean 
last post by:
The energy model is structured as follows and uses excel sheets to give input data:
1Utility.py contains all the functions needed to calculate the variables and other minor things (mentions...

by: Teri B 
last post by:
Hi, I have created a subform Roles. In my course form the user selects the roles assigned to the course.
0netomany. One course many roles.
Then I created a report based on the Course form and...

by: nia12 
last post by:
Hi there,
I am very new to Access so apologies if any of this is obvious/not clear.
I am creating a data collection tool for health care employees to complete. It consists of a number of...

by: NeoPa 
last post by:
Introduction
For this article I'll be focusing on the Report (clsReport) class. This simply handles making the calling Form invisible until all of the Reports opened by it have been closed, when it...

by: isladogs 
last post by:
The next online meeting of the Access Europe User Group will be on Wednesday 6 Dec 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
In this month's session, Mike...
 