# The shortest path extraction

Figures 3.1 and 3.2 represent a subset of the experimental network, treated respectively as directed and undirected graphs. Each graph consists of such nodes as: *chleb* “bread”, *maslo* “butter”, *jedzenie* “food”, *ser *“cheese”, *mleko* “milk”, *dobry* “good”, *kanapka* “sandwich” and *zolty *“yellow” linked by connections produced by the free word association experiment.

Figure 3.1 represents the concept of normalizing the directed network, if a path shorter than the one directly linking two nodes can be found. “Shorter” in this case means that the sum of weights of the path connections is smaller than the weight of the direct connection. On this specific example, the dotted connection between the nodes is replaces the original black one. It is caused by the fact that the path *ser ^jedzenie ^ chleb ^ maslo* has a weight sum of 84, which is lower than the direct connection weight of 200 for the nodes *maslo ^ ser.*

The same reasoning applies to the experimental net being represented by an undirected weighted graph (Figure 3.2).

**Figure 3.1. ***Shortest path for a directed network. For a color version of this figure, see www.iste.co.uk/sharp/cognitive.zip*

**Figure 3.2. ***Shortest path for an undirected network. For a color version of this figure, see www.iste.co.uk/sharp/cognitive.zip*

In the case of the undirected graph, we treat it just as a directed graph with symmetrical connections between nodes, i.e. *(v1,v2)* = (v2, *v1).* We can see from Figure 3.2 that the connection *ser - maslo* is replaced by the same path *ser -jedzenie - chleb - maslo* as in the directed graph, and that another shortest path for the *ser - maslo* connection is found, i.e. the path *maslo - mleko - ser**,* with a path weight of 198 which is smaller than 200, which is the weight of the *ser - maslo* direct connection.

In both cases, the Dijkstra’s classic shortest path algorithm has been applied. However, the sub-graph extracting algorithm *NEA* will reject any shortest path which does not meet the condition set by the *l* parameter.