0

Generic Dijkstra with min heap implementation JAVA

I am having problems with the jmpkemetqtion of a graph library in witch I have also a method called dijkstra that find all the shortest path from a graf starting by a source. All these have to be generics The problem is the use of a generic Vertex as type of the min heap. In my Vertex I have ONLY the generic type of a attribute called label. NO other attribute Thank you to all that will answer and try to help me, I'm going to see all the suggestion

12th Nov 2022, 1:44 PM
Michele
Michele - avatar
2 Answers
+ 4
You can check the Sololearn lesson about the Graph data structure. There are code examples and some useful insights in the comments too. https://www.sololearn.com/learn/656/?ref=app The vertex or node in the graph, really doesn't have to store any numeric data. The important thing that would be used for the Dijkstra algorithm, is the edges of the graph which connect the vertices, and describe their 'distance'. Linking your code would be helpful in explaining what is the trouble.
12th Nov 2022, 2:59 PM
Tibor Santa
Tibor Santa - avatar
0
Tibor Santa, so in my impelentation When i call dijkstra on a graph and a starting vertex I have to put the distance of all the vertex, from turin to Infinity (by setting the weight of the edge between start and the vertex?), then I have to insert these edges with infinity weight, from the start vertex, and puth the edge that has from and to the start, as 0 (so my min heap puts it in the root) Then cycling until the priority q is empty by extraction the edge with min weight of the q, and adding in the shortest path, then relaxing the "to" adj vertices by decreasing the key of the adj vertex But I keep dont jndestrandi how in the returned graph I can keep track of all the shortest path from the source In the internt I see only version with an attribute "weight" in the vertex, but it doesnt have to have one
12th Nov 2022, 3:10 PM
Michele
Michele - avatar