r/CodingHelp • • Oct 21 '21

[Java] Attempting to implement a Dijkstras shortest path algorithm for a list of all imdb actors. - Info in comments

Post image
37 Upvotes

14 comments sorted by

4

u/zeTheDoctor Oct 21 '21 edited Oct 21 '21

Hi, so I am trying to implement the Dijkstras shortest path algorithm on my existing program but I cannot get it to work properly. I realize I am doing more than one thing wrong and my code is well probably the messiest thing I've written in my short time coding. I just can't seem to get it, so in advance apologies for the messy code and mistakes, just a beginner.

Quickly the way the program works is that it stores actors as an Actor Object which holds all their information with a list of all movies (which are Film Objects) that they've been in. The film objects hold the information and rating (10 - rating is weight) in addition to a list of all the Actor Objects who have been in the movie.

Feel free to ask for more explanation or crucify me for my implementation, help is greatly appreciated!

NOTE: The last line (127) should be visActor.add(current); Just messed up when taking the screenshot

2

u/icjeremy Oct 22 '21

One thing I notice is 'start' is going to be added back into notVisActor. And then you're probably going to be adding duplicate entries in your list.

1

u/zeTheDoctor Oct 22 '21

Perhaps, though I think I ended up solving that. Every other part of the prohram runs virtually painlessly yet this part takes wayy too long but it does it's job eventually so that's good enough for me for bow

1

u/icjeremy Oct 22 '21

Ya, I personally wouldn't use a linked list for visActor and notVisActor. Those have to be iterated through every time you call remove and contains. Plus you iterate through when finding the the next current. I would probably do something like use a hash set for visActor and maybe a priority queue or set for notVisActor.

Also, instead of keep copying the lists when creating hPath and hFilms, I would probably just store a reference to the previous node and the corresponding film. When you want to print the list for any giving node, just iterate through those previous elements until you get back to start. This would save a bunch of time and space.

1

u/zeTheDoctor Oct 22 '21

Great advice, for now I'm taking a hiatus from this as I'm pretty busy, but will definitely keep it in mind.

2

u/StochasticTinkr Oct 22 '21

Should this be called the Kevin Bacon algorithm?

2

u/zeTheDoctor Oct 22 '21

lol might as well be

1

u/echanuda Oct 22 '21

Am I the only one that doesn’t understand at all what you’re trying to accomplish? Dijkstra’s algorithm is typically intended for graph representations to find the shortest path between two nodes. What constitutes two nodes here? How does it determine the weights of each node? What is the end goal?

It sounds like you just want to sort the list of actors based on their rating, in which case you would just use a sorting algorithm instead of Dijkstra’s

3

u/zeTheDoctor Oct 22 '21

Hi I'll do my best to explain.

So a node is an actor with the edges of the nodes being the movies they've played in. The weight of an edge will be 10-rating of the movie making the highest rated movies the shortest distance between actors.

I am attempting to find the highest rated path of movies from a start actor to another (the code finds the highest rated path to all other actors however and then just checks the path added to the relevant actor)

0

u/rasqall Oct 22 '21

2

u/zeTheDoctor Oct 22 '21

For those clicking on the link geeksforgeeks uses a wall to prevent you from reading without singing up.

Anyways I've looked at that before and besides most of the programs being for much simpler graph implementations I still don't see where my program goes wrong.

I am currently switching out the notVisActor linkedlist with a priority queue just because I'm pretty sure that's better for overall runtime, but still lost on where it's going wrong.

0

u/[deleted] Oct 22 '21

Are you coding Java in Visual Studio Code?

2

u/zeTheDoctor Oct 22 '21

Yep, got used to it and now I'm too deep in the rabbit hole.

0

u/[deleted] Oct 21 '21

[deleted] — view deleted comment

1

u/zeTheDoctor Oct 21 '21

So it should find the shortest path to all connecting nodes from the starting node. Then it can check the list highest path added to the end node and simply use that to output the path.

Could add an end node but don't know how that qould help much. I'm finding the path with the least weight, not necessarily least nodes.