Graph Theory: Dijkstra's Algorithm

In summary, the conversation is about Dijkstra's Algorithm and the confusion surrounding its implementation in both tabular and graphical form. The participants discuss their understanding of the algorithm and its application, as well as their difficulties and questions. They also mention finding errors in the provided solutions and the reasoning behind certain choices.
  • #1
wubie
Hello,

Does anyone know of an online resource which explains Dijkstra's Algorithm both in tabular form and graphical form?

My text does an incredibly poor job explaining this algorithm. I sort of understand it graphically. But I have absolutely no idea what is going on when it comes to implementing it in tabular form.

Here is a question which requires me to use Dijkstra's Algorithm. I have the answer both in tabular and graphical form, but I am running into problems understanding the answer in graphical form and I have NO idea what is going on with the tabular form.

A graph has 11 vertices labelled A to K, and the following 18 edges with their lengths given:

AB(8), AC(5), AD(7), BE(6), BF(2), CE(4), CF(5), DF(4), DG(2), EH(4), FH(4), FI(2), FJ(4), GI(2), GJ(4), HK(4), IK(5), JK(4).

Apply Dijkstra's Algorithm to construct a shortest-path spanning tree from the vertex A.

I understand the first choice: AC.
I now look at the fringe vertices of vertex A and C. I pick AD.
I now look at the fringe vertices of A,C,and D. I pick AB.
I now look at the fringe vertices of B,C,and D. Now do I pick DG or CE? And why? The answer is CE but I don't know why.

My text does not explain what to do in this situation. And the answer does not state its reason for choosing CE over DG.

Any help is appreciated. Thankyou.



Right. I just looked at the answer in tabular form and I think I can follow what is going on in tabular form. But I still don't understand the reasoning of choosing CE over DG.
 
Last edited by a moderator:
Mathematics news on Phys.org
  • #2
Because it came first in the list!

Both the path ADG and the path ACE have the same weight 9; neither is better than the other. You have to make a choice, and "pick the first one in case of a tie" is as reasonable of a strategy as any.
 
  • #3
Alright. Thanks Hurkyl.

I found out why I couldn't figure out the tabular form. There was a couple of typo's in the table.

Cheers.
 
Last edited by a moderator:

1. What is Dijkstra's algorithm and how does it work?

Dijkstra's algorithm is a graph theory algorithm used to find the shortest path between two vertices in a graph. It works by assigning a distance value to each vertex and continually updating the values until the shortest path is found. It also keeps track of the previous vertex in the path, allowing it to backtrack and find the complete path.

2. What is the time complexity of Dijkstra's algorithm?

The time complexity of Dijkstra's algorithm is O(E + VlogV), where E is the number of edges and V is the number of vertices in the graph. This makes it a relatively efficient algorithm for finding the shortest path in a graph.

3. Is Dijkstra's algorithm guaranteed to find the shortest path?

Yes, Dijkstra's algorithm is guaranteed to find the shortest path between two vertices in a graph, as long as there are no negative edge weights. If there are negative edge weights, the algorithm may not find the correct shortest path.

4. What are the applications of Dijkstra's algorithm?

Dijkstra's algorithm has various applications in real-world problems, such as finding the shortest route for navigation systems, optimizing network routing, and finding the fastest delivery route for logistics companies. It can also be used in data structures like priority queues and heaps.

5. Are there any limitations to Dijkstra's algorithm?

One limitation of Dijkstra's algorithm is that it does not work for graphs with negative edge weights. It also requires the entire graph to be known beforehand, so it may not be suitable for large or dynamically changing graphs. Additionally, it may not always find the optimal path if there are multiple paths with the same weight.

Similar threads

  • General Math
Replies
5
Views
984
  • General Math
Replies
21
Views
1K
  • General Math
Replies
13
Views
1K
Replies
3
Views
1K
  • General Math
Replies
2
Views
1K
  • Programming and Computer Science
Replies
1
Views
888
  • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
  • General Math
Replies
1
Views
1K
Back
Top