Abstract/Introduction

A cognitive task analysis investigates the physical tasks, cognitive plans, and the required knowledge that a user needs in order to achieve a particular work model (MIT source).  In this paper I will perform a cognitive task analysis of Dijkstra’s Algorithm, which is famously known for being used to find the shortest distance between two points on a map.  I will then use the Functional Information Processing Model (FIPM) to discuss this task analysis.  I will first provide the facts and the necessary background information that are required to understand Dijkstra’s Algorithm.  Then I will use propositional networks, visual images, procedures and mechanisms to create a mental model and describe how Dijkstra’s Algorithm should be used and implemented.  Then I will show how these different types of knowledge representations can be used to lay the basis of a Knowledge-Based Instructional Design for teaching Dijkstra’s Algorithm to students.   Lastly, I will provide appropriate instructional strategies that make use of the different types of knowledge representation to resolve specific problems via Dijkstra’s Algorithm.

General Knowledge

In 1956 the Dutch computer scientist Edsger Dijkstra conceived an algorithm that solved the single-source shortest path problem for a graph with nonnegative edge path costs. 

The algorithm, which is based on a graph that is made up of paths that intersect at different nodes, determines the path with the lowest cost between an initial node and every other node. Any two nodes are connected by an directed edge, and the path between any two nodes is made up of at least one edge.

As a result, Dijkstra’s algorithm is now often used to solve common real world routing problems such as finding the shortest path between two cities given certain constraints such as distance and direction.

In the world of computing Dijkstra's Algorithm is now known to be a greedy algorithm.  This is because this algorithm makes the most efficient choice at each step.  Therefore, the idea behind this rational is that a series of optimal decisions will lead to an optimal final decision.  Thus, Dijkstra's algorithm is like a function that computes the optimal cost/path between the origin and all other nodes on the graph.

Factual/Declarative Knowledge and Propositional Networks

Declarative knowledge is knowledge that we can talk about (notes).  Based on this knowledge we know that “something is the case” when applying Dijkstra’s algorithm to find the shortest path/cost between two nodes. This type of knowledge can be represented through propositional networks, which connect the concepts and objects involved in Dijkstra’s algorithm.

1^st proposition:

Dijkstra’s Algorithm (isa, optimization method, Graph/Network of Nodes)

In this proposition isa is the pointer that defines Dijkstra’s Algorithm both as an optimization method and a network of nodes.

2^nd proposition:

Dijkstra’s Algorithm (compute, shortest distance, lowest cost, shortest time)

This proposition indicates the uses of Dijkstra’s Algorithm. Shortest distance, lowest cost and shortest time are the concepts, and compute is the pointer that explains what Dijkstra’s Algorithm is used for.

3^rd proposition:

Running time (affect, Dijkstra’s Algorithm)

This proposition explains that one of the factors that affect Dijkstra’s Algorithm is the running time, which is how long it takes to complete the algorithm. Because the running time is greater then zero, since the algorithm needs to take place, this is a factor that will have a negative influence.

4^th proposition:

Shortest distance (used by, Online routing systems, GPS units)

This sentence points out the entities that make use of the concept of shortest distance.

5^th proposition:

Google Maps, Mapquest (type of, online routing system)

This proposition explains that the entities Google Maps and Mapquest are types of online routing systems.

6^th proposition:

Tom Tom, Garmin (type of, GPS units)

This proposition explains that the entities Tom Tom and Garmin are types of GPS units.

7^th proposition:

Lowest Cost (used by, Economists, Investment Bankers, Flight booking systems)

This is a positive relation, which uses the pointer used by to indicate that the concept of lowest cost is used by economists, investment bankers, flight booking systems.

8^th proposition:

Expedia, BookIt (type of, flight booking system)

This proposition uses the pointer type of to connect the concept of booking system with the instances Expedia and BookIt.

9^th proposition:

Shortest time (used by, flight booking system)

This proposition indicates that the concept of shortest time is used by flight booking systems.

System Diagrams / Mental Model

– Uses –

                  – Structure –

- Functioning - 

Imagery Knowledge / Example of Dijkstra's Algorithm

Step 1

We will start out at A, the origin, and see what other nodes we can get to from this point.  Firstly, the initial cost from A to any node is infinity, but this cost changes once we travel the paths connecting A to other nodes.  We will determine which nodes we can access from A directly. We will keep track of our findings, which will lead to the shortest path, by recording them in the table to the left of the graph.

We look at the paths that originate in A.  There is a path from A to B at cost 20.  20 is less than infinity, which was the initial cost from A to all nodes.  Therefore we record the new lowest cost from A to B in our table as the alphanumeric number 20A. This number represents the cost, 20, from the node of origin, A.  The next path that originates in A leads to D and its cost is 80. 80 is less than infinity, so we record the new lowest cost from A to D in our table as 80A. The last path that originates in A leads to G and its cost is 90.  90 is less than infinity, so we record the new lowest cost from A to G in our table as 90A.  The cost from A to all of the other nodes will be infinity because there are no direct paths from A to any of them, yet.

Step 2

Dijkstra’s Algorithm always makes the most efficient choice at each Step, and this is reflected in how we pick the next node. We find out which was the lowest cost path in Step 1 and which node it lead to. That will be the node through which we will now compute the lowest path cost to other nodes.

The lowest cost path in Step 1 was 20A from A to B.  Therefore in Step 2 the search for the lowest cost path begins with node B.  There is only one edge originating in B, and this edge leads to node F. The cost to get to F via B is 10 more than the cost to get to B. Therefore, the new shortest path from A to F is 30B where 30 represents the total cost of the path and B represents the last node that was traversed by this path.  None of the other path costs have changed, therefore we copy them over from Step 1 to Step 2.

Step 3

We find out which was the lowest cost path in step 2, and which node it has taken us to. In this search we exclude those paths that we have already picked like the path from A to B, which has resulted into a cost of 20. Therefore, the next lowest cost path is 30B and it leads to node F.  Therefore the search will now start with node F.

There are two edges originating in F.  The first one connects F to C at a cost of 10, making the lowest cost path from A to C 40. We record this in our table as 40F, where 40 represents the new lowest total cost from A to C and F is the node that made this path possible.  The next edge originating in F connects node F to node D at a cost of 40, making the total cost from A to D 70.  Since our current cost from A to D is 80, and the new cost is 70, we will record the new lowest cost path from A to D as 70F. None of the other path costs from A to the other nodes have changed. So we copy them over as they appear in Step 2.

Step 4

We find out which was the lowest cost path in Step 3, and which node it has taken us to. Again, in this search we exclude those paths that we have already picked like the path from A to B, which has resulted into a cost of 20 or the path from B to F, which has resulted into a cost of 30. Therefore, the next lowest cost path is 40F and it leads to node C.  The search will now start with node C.

There are three edges originating from node C.  The first one connects node C to node F and its cost is 50, making the total cost from node A to node F 90.  A cost of 90 is greater than our current cost from A to F, which is 30.  Therefore, we discard it and copy over the current cost.  The next edge originating in C connects node C to node H and has a cost of 20, making the total cost from A to H 20.  Since the current cost of getting to H from A is infinity, we discard it and record the new lowest cost path from A to H as 60C. The last edge originating in C connects node C to node D at a cost of 10, making the total cost of getting to D from A cost 50.  This cost is less than our current cost which is 70, so we discard the current cost of getting to D from A, and record the new lowest cost which is 50C. None of the other path costs from A to the other nodes have changed. So we copy them over as they appear in Step 3.

Step 5

We find out which was the lowest cost path in Step 4 and which node it has taken us to. Again we exclude those paths that we have already picked. Therefore, the next lowest cost path is 50B and it leads to node D.  Therefore the search will now start with node D.

There is only one edge originating in D and leading to node G making the total cost of getting from A to G 70.  This new cost is less than the current cost with is 90 via node A. We therefore discard the current cost and replace it with the new lowest cost path which is 70D. None of the other path costs from A to the other nodes have changed. So we copy them over as they appear in Step 4.

Step 6

Looking at the costs that we have recorded in Step 5, and excluding those that we have already investigated, we see that the next lower cost path leads to node H.  However, there are no edges originating in from this node.  Therefore, we copy over all the costs as they appear in step 5.

Step 7

Looking at the costs that we have recorded in Step 5, and excluding those that we have already investigated, we see that the next lowest cost path is 70D, which leads to node G. Therefore, we will start the search with node G.

There is only one edge originating from node G. This edge connects node G to node A at a cost of 20 making the total cost of getting from A to G 90G.  However, this is the same cost as the current cost, so we will discard it. All costs will be copied over just as they appear in Step 6.

Step 8

There is one last path that we have to look at, and this is the path the leads to node E.  However, node E has a value of infinity, and as the graph point out, there is really no path that leads to E. Therefore, there is no way of getting to E.

According to our findings, the shortest path from node A to all other nodes in the graph is outlined in Step 7. 

Mechanisms

Knowledge-Based Instructional Design

Conclusion

References