Finding Shortest Path in G: Dijkstra's Algorithm

In summary, the conversation was about finding the weights of the shortest path from s in a directed graph using Dijkstra's Algorithm. The graph had 5 vertices and 9 edges with corresponding weights. The output of the algorithm was d[s]=0, d[a]=5, d[b]=11, d[c]=9, and d[d]=3. The participants agreed that this was the correct result.
  • #1
mathmari
Gold Member
MHB
5,049
7
Helloo!

I am asked to find the weights of the shortest path from s in a directed Graph G=(V,E), where V={s,a,b,c,d}, E={(s,a),(s,d),(a,b),(a,c),(a,d),(b,s),(b,c),(c,b),(d,a)} and their weights 5,3,6,4,1,3,7,2,2...
I used Dijkstra's Algorithm, and I found d=0,d[a]=5,d=11,d[c]=9,d[d]=3... Is this correct??
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
mathmari said:
Helloo!

I am asked to find the weights of the shortest path from s in a directed Graph G=(V,E), where V={s,a,b,c,d}, E={(s,a),(s,d),(a,b),(a,c),(a,d),(b,s),(b,c),(c,b),(d,a)} and their weights 5,3,6,4,1,3,7,2,2...
I used Dijkstra's Algorithm, and I found d=0,d[a]=5,d=11,d[c]=9,d[d]=3... Is this correct??


That's what I get as well.
 
  • #3
Great...! :) Thank you!
 

Related to Finding Shortest Path in G: Dijkstra's Algorithm

1. What is Dijkstra's algorithm?

Dijkstra's algorithm is a popular algorithm used to find the shortest path between two nodes in a graph. It was developed by Dutch computer scientist Edsger Dijkstra in 1956.

2. How does Dijkstra's algorithm work?

Dijkstra's algorithm works by finding the shortest path from a starting node to all other nodes in a graph. It does this by maintaining a list of distances from the starting node to each node in the graph and continually updating those distances as it explores the graph. It also keeps track of the previous node on the shortest path to each node, allowing it to reconstruct the shortest path once the destination node is reached.

3. What are the advantages of using Dijkstra's algorithm?

Dijkstra's algorithm is a highly efficient and accurate way to find the shortest path between two nodes in a graph. It guarantees to find the shortest path and is also relatively easy to implement. Additionally, it can handle weighted graphs and graphs with negative edge weights, making it a versatile algorithm for various applications.

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

One of the main limitations of Dijkstra's algorithm is that it does not work on graphs with negative cycles. This means that if there is a cycle in the graph where the sum of the edge weights is negative, Dijkstra's algorithm will not be able to find the shortest path. Additionally, it is not suitable for use on very large graphs as it has a time complexity of O(E log V), where E is the number of edges and V is the number of vertices.

5. In what applications is Dijkstra's algorithm commonly used?

Dijkstra's algorithm is commonly used in various applications such as route planning, network routing protocols, and computer networks. It is also used in transportation and logistics for finding the shortest path between locations and in social networks for finding the shortest path between users. Additionally, it is used in many other fields such as biology, chemistry, and economics.

Similar threads

MHB Applying Dijkstra Algorithm: Solving a Problem
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
Comp Sci Using Single Source Shortest Path Algorithm to find the longest path
    • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
MHB Please help with bool algebra and logic things
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
I Is an algorithm for a proof required to halt?
    • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
I Is A→E→D→F a valid solution for Dijkstra's algorithm?
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
I Intro to Symbolic Logic: Replacement Rules
    • Set Theory, Logic, Probability, Statistics
Replies
8
Views
1K
MHB Relation Algebra - Relational Calculus
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
768
I Traffic simulation : directed graph including specific rules
    • General Math
Replies
5
Views
1K
Solving Number Triangle Puzzle with Trial and Error
    • Precalculus Mathematics Homework Help
Replies
21
Views
671
MHB How Do You Calculate the Total Weight of a Huffman Code?
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
819

Hot Threads

Recent Insights

Back
Top