I am trying to learn some more stuff about graphs and Dijkstra's Algorithm, so I have a function that randomly generates a weighted undirected graph, saves in a file like this:
numbers_of_vertices number_of_nodes
node_a node_b distance_from_a_to_b
etc.
And then I run Dijkstra's to output the distances from node 0 to all the other nodes, but sometimes the distance from node 0 to other nodes is 0, that means that there is no connection from node 0 to that node?
Also I have another question, with what kind of graphs Dijkstra's works?>br>
Thanks for the help!
Dijkstra's algorithm is a variation of a BFS traversal. The difference is, it utilizes a min heap to traverse to the closest node every time.
Your function that randomly generates a weighted undirected graph should not create a pair of nodes where node_a and node_b have a distance of 0. This means the node is in the same exact place - thus, no need to traverse.
Dijkstra's algorithm works on any weighted graphs (with positive only weights) where you have a starting and an end condition.
Here's a 10 minute video explaining the algorithm: https://www.youtube.com/watch?v=pVfj6mxhdMw