optimisation algorithms

• What is Dijkstra’s shortest path algorithm used for?

  Calculating the shortest path between points
• What do nodes represent in weighted graphs?

  Labelled circles also known as vertices
• What do edges represent in weighted graphs?

  Connections between nodes with a weight
• What is the least cost path in shortest path problems?

  The best way to get from one node to another
• How is the shortest path calculated?

  By adding up individual weights from edges
• What does the shortest path consist of?

  Sequence of nodes visited for minimum cost
• What information does Dijkstra's algorithm produce for each node?

  Node label, cost, previous node label
• What is the initial cost of all nodes in Dijkstra's algorithm?

  Infinity, indicating costs not calculated
• What is the cost of the start node A in Dijkstra's algorithm?

  0, as it is the starting point
• What is the purpose of the unvisited list in Dijkstra's algorithm?

  To track nodes that have not been visited
• What happens when a node is added to the visited list?

  It cannot be revisited in the algorithm
• What does the algorithm do after picking the current node?

  Examines reachable unvisited nodes from it
• What is updated for neighbors in the current node?

  The cost for all neighbors is updated
• What is the process repeated until in Dijkstra's algorithm?

  Until the desired end node is reached
• What is a limitation of Dijkstra's algorithm?

  It can be inefficient for specific targets
• What does Dijkstra's algorithm not consider?

  Direction or proximity of nodes
• What is an alternative to Dijkstra's algorithm?

  A* pathfinding algorithm
• What are the steps involved in Dijkstra's shortest path algorithm?

  1. Initialize costs of all nodes to infinity.
  2. Create unvisited list with nodes and costs.
  3. Set start node cost to 0.
  4. Create an empty visited list.
  5. Pick the node with the lowest cost.
  6. Examine reachable unvisited nodes.
  7. Update costs for neighbors.
  8. Add current node to visited list.
  9. Repeat until the end node is reached.
• What are the strengths and weaknesses of Dijkstra's algorithm?

  Strengths:

  • Finds shortest path efficiently for all nodes.
  • Works well with weighted graphs.

  
  

  Weaknesses:

  • Inefficient for specific target searches.
  • Does not consider direction or proximity.