18. Artificial Intelligence
1. Dijkstra’s Algorithm
Shortest path algorithms:
● Designed to find the optimal/shortest/most cost-effective route/paths between two nodes/from
a source (start) node to another node in the graph, based on distance/cost/time
● The graph must be weighted (which could represent distances/time/cost of travel)
● The algorithm can be used with both directed and undirected graphs
Applications of shortest-path algorithms/graphs in AI:
● A graph is used in AI to record relationships between entities, using vertices/nodes and edges
● E.g. to represent places on a map/the distances between them, in order to find the shortest route
● Other applications include routing packets over the Internet, and GPS
Implementing Dijkstra’s algorithm:
● The implementation of the algorithm is similar to a breadth first search
● Uses a priority queue as the supporting data structure to keep record of which node to visit next -
the priority queue will always have the node with the lowest temporary value at the front
● Process (helpful to understand -https://www.youtube.com/watch?v=YHDmA7ZlwqU):
○ Start by assigning a temporary distance value to each node - the temporary distance is 0 at
the start node, and ∞ at every other node
○ All nodes are marked as not visited
○ Set the current node to be the first node in the priority queue
○ For each of the current node’s neighbours, calculate the distance to the neighbour from
the source, by adding the edge weight to the current node’s temporary value - if this is
lower than the neighbour’s temporary value, update it to this
○ Once all of the neighbours have been looked at, mark the current node as visited and
remove it from the priority queue
○ Repeat from step 3 until all of the nodes have been visited
1. Dijkstra’s Algorithm
Shortest path algorithms:
● Designed to find the optimal/shortest/most cost-effective route/paths between two nodes/from
a source (start) node to another node in the graph, based on distance/cost/time
● The graph must be weighted (which could represent distances/time/cost of travel)
● The algorithm can be used with both directed and undirected graphs
Applications of shortest-path algorithms/graphs in AI:
● A graph is used in AI to record relationships between entities, using vertices/nodes and edges
● E.g. to represent places on a map/the distances between them, in order to find the shortest route
● Other applications include routing packets over the Internet, and GPS
Implementing Dijkstra’s algorithm:
● The implementation of the algorithm is similar to a breadth first search
● Uses a priority queue as the supporting data structure to keep record of which node to visit next -
the priority queue will always have the node with the lowest temporary value at the front
● Process (helpful to understand -https://www.youtube.com/watch?v=YHDmA7ZlwqU):
○ Start by assigning a temporary distance value to each node - the temporary distance is 0 at
the start node, and ∞ at every other node
○ All nodes are marked as not visited
○ Set the current node to be the first node in the priority queue
○ For each of the current node’s neighbours, calculate the distance to the neighbour from
the source, by adding the edge weight to the current node’s temporary value - if this is
lower than the neighbour’s temporary value, update it to this
○ Once all of the neighbours have been looked at, mark the current node as visited and
remove it from the priority queue
○ Repeat from step 3 until all of the nodes have been visited
