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).

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

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

Shortest path for an undirected 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.

 
Source
< Prev   CONTENTS   Source   Next >