Shortest Path Algorithms and AI

Using the figure above, what is the shortest path of D for the Dijkstra algorithm? (imagine that this map is to scale)

• C

• E

Using Dijkstra Algorithm, that is the shortest path of C?

• A

• B

• E

• D

Using Dijkstra Algorithm, that is the shortest path of C?

• A

• B

• E

• D

Select all correct applications of a shortest-path algorithm

• Navigation

• NPC control in gaming

• Sending data packets

• Buying Crypto

• Targeted advertising

Optimisation algorithms are designed to find the (a)   path from a start node to any other node

Starting at node S, what is the minimum cost to reach node G?

• S-A-B-F-G

• S-A-B-C-G

• S-A-B-C-H-G

• S-A-B-C-E-H-G

Starting at node S, what is the value of the shortest path to node G?

(a)  

Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijstra?s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.

• SDT

• SBDT

• SACDT

• SACET

Dijkstra’s single source shortest path algorithm when run from vertex a in the below graph, computes the correct shortest path distance to

• only vertex a

• only vertices a,e,f,g,h

• only vertices a,b,c,d

• all the vertices

What is the Dijkstra's algorithm cost for traveling from A to C

(a)