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!
 

FAQ: Finding Shortest Path in G: Dijkstra's Algorithm

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.

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.

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.

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.

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
Replies
6
Views
2K
I Is A→E→D→F a valid solution for Dijkstra's algorithm?
Replies
1
Views
1K
MHB Please help with bool algebra and logic things
Replies
2
Views
1K
Comp Sci Using Single Source Shortest Path Algorithm to find the longest path
Replies
4
Views
1K
I Intro to Symbolic Logic: Replacement Rules
Replies
8
Views
2K
B Shortest distance between two points
Replies
11
Views
737
MHB Relation Algebra - Relational Calculus
Replies
6
Views
1K
Combinatorial Algorithm for Sorting Adjacency Matrices in Polynomial Time
Replies
4
Views
1K
MHB Proving $\delta(s,u)+w(u,v)=\delta(s,v)$ in a Shortest Path
Replies
2
Views
1K
MHB Is it the algorithm the optimal one?
Replies
20
Views
4K

Hot Threads

Recent Insights

Back
Top