#Dijkstras help!

1 messages · Page 1 of 1 (latest)

wary bolt
#

Hi guys! Got to do Dijkstras for a school project. Been stuck on it approx 50 hours. Anyone mind helping? Any help greatly appreciated.

hazy briarBOT
#

<@&987246399047479336> please have a look, thanks.

#

Here is an AI assisted attempt to answer your question 🤖. Maybe it helps! In any case, a human is on the way 👍. To continue talking to the AI, you can use </chatgpt:1108714622413963314>.

#
TJ-Bot
Hi guys! Got to do Dijkstras for a school project. Been stuck on it approx 50 hours. Anyone mind helping? Any help greatly appreciated.

Sure, we can help with that! Dijkstra's algorithm is a popular algorithm for finding the shortest path between nodes in a graph. Here's a high-level overview of how it works:

  1. Initialize the distance to all nodes as infinity, except the starting node which is 0.
  2. Create a priority queue and add the starting node to it with distance 0.
  3. While the priority queue is not empty, extract the node with the smallest distance.
  4. For each neighbor of the extracted node, calculate the new distance as the sum of the extracted node's distance and the edge weight between them.
  5. If this new distance is smaller than the current distance to the neighbor, update it and add the neighbor to the priority queue.
  6. Repeat steps 3-5 until all nodes have been visited.

You can implement this algorithm using Java and data structures like PriorityQueue and HashMap to store distances. Make sure to handle edge cases like disconnected nodes or negative edge weights carefully.

If you have specific questions or issues with your implementation, feel free to ask for more help here! Good luck with your project!

- AI generated response
stable python
pastel flicker
#

always here to help. but it seems u havent asked any concrete question, so u kinda missed my time window now :0

#

no idea where ur stuck, as u havent shared anything unfortunately, but i guess i can drop some stuff while im here:

#

usually i explain dijkstra as the logical extension of BFS on weighted graphs

#

for bfs, here is a good base to work with:

hazy briarBOT
#

Graph traversal can be accomplished easily using BFS or DFS. The algorithms only differ in the order in which nodes are visited: https://i.imgur.com/n9WrkQG.png

The code to accomplish them is identical and only differs in the behavior of the Queue they are based on. BFS uses a FIFO-queue and DFS a LIFO-queue.

Queue<Node> nodesToProcess = ... // depending on BFS or DFS
nodesToProcess.add(rootNode); // add all starting nodes

Set<Node> visitedNodes = new HashSet<>();
while (!nodesToProcess.isEmpty()) {
  // Settle node
  Node currentNode = nodesToProcess.poll();
  if (!visitedNodes.add(currentNode)) {
    continue; // Already visited before
  }

  // Do something with the node
  System.out.println(currentNode); // Replace by whatever you need

  // Relax all outgoing edges
  for (Node neighbor : currentNode.getNeighbors()) {
    nodesToProcess.add(neighbor);
  }
}

To get BFS, use a FIFO-queue:

Queue<Node> nodesToProcess = new ArrayDeque<>();

And for DFS a LIFO-queue:

Queue<Node> nodesToProcess = Collections.asLifoQueue(new ArrayDeque<>());

Thats all, very simple to setup and use.

For directed graphs relax all outgoing edges.
For trees the visitedNodes logic can be dropped, since each node can only have maximally one parent, simplifying the algorithm to just:

Queue<Node> nodesToProcess = ... // depending on BFS or DFS
nodesToProcess.add(rootNode); // add all starting nodes

while (!nodesToProcess.isEmpty()) {
  // Settle node
  Node currentNode = nodesToProcess.poll();

  // Do something with the node
  System.out.println(currentNode); // Replace by whatever you need

  // Relax all outgoing edges
  for (Node child : currentNode.getChildren()) {
    nodesToProcess.add(child);
  }
}
zabuzard • used /tag id: bfs ·
pastel flicker
#

now, knowing bfs, dijkstra is just one step ahead

#

in a nutshell u just swap out the Queue that BFS uses against a PriorityQueue

#

and that's it

#

for the priorityqueue, the sorting criteria is on what's called the tentative distance

#

which u maintain as u explore the graph

stable python
#

the hardest part is to create correctly the weight function

pastel flicker
#

for example in a separate Map<Node, Double> or, if ur having nodes as simple integers, perhaps also as normal array double[]

#

but thats details

#

also, remember that u first have to fully understand an algorithm before u start coding

#

so possibly u should step back, grab pen and paper and try to visualize whats going on, drawing the typical process of dijkstra that's also shown on all the illustrations and animations

#

wikipedia has a great example + animation

wary bolt
#

Alright cool thanks!

#

Ive put my laptop away for now but basically i was putting it into a game and it was gonna be grid based?

pastel flicker
#

dijkstra itself doesnt care the slightest how ur graph looks like or if its a grid or not

#

it works on any graph (with positive edge weights)

#

and a grid is a graph as well. each cell a node, edges that connect a cell to its adjacent cells etc

#

👍