Finding Shortest Path in G: Dijkstra's Algorithm

  • Context: MHB 
  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Algorithm Path
Click For Summary
SUMMARY

The discussion centers on the application of Dijkstra's Algorithm to determine the shortest path weights in a directed graph G with vertices V={s,a,b,c,d} and edges E={(s,a),(s,d),(a,b),(a,c),(a,d),(b,s),(b,c),(c,b),(d,a)}. The weights assigned to the edges are 5, 3, 6, 4, 1, 3, 7, 2, and 2, respectively. The calculated shortest path weights are d[s]=0, d[a]=5, d[b]=11, d[c]=9, and d[d]=3, which are confirmed as correct by another participant in the discussion.

PREREQUISITES
  • Understanding of Dijkstra's Algorithm for shortest path finding
  • Familiarity with directed graphs and their representation
  • Knowledge of graph theory terminology, including vertices and edges
  • Basic programming skills to implement algorithms
NEXT STEPS
  • Implement Dijkstra's Algorithm in Python using the NetworkX library
  • Explore the time complexity of Dijkstra's Algorithm and its implications
  • Learn about alternative shortest path algorithms, such as Bellman-Ford
  • Study the application of Dijkstra's Algorithm in real-world scenarios, such as GPS navigation
USEFUL FOR

Students, software developers, and data scientists interested in graph algorithms and their practical applications in computing and optimization.

mathmari
Gold Member
MHB
Messages
4,984
Reaction score
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
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.
 
Great...! :) Thank you!
 

Similar threads

  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 11 ·
Replies
11
Views
2K
  • · Replies 6 ·
Replies
6
Views
1K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 2 ·
Replies
2
Views
1K
  • · Replies 20 ·
Replies
20
Views
4K