Deprecated: Methods with the same name as their class will not be constructors in a future version of PHP; plgContentJComments has a deprecated constructor in /var/www/astarmathsandphysics/plugins/content/jcomments/jcomments.php on line 25 Call Stack: 0.0000 362392 1. {main}() /var/www/astarmathsandphysics/index.php:0 0.0480 1211736 2. Joomla\CMS\Application\SiteApplication->execute() /var/www/astarmathsandphysics/index.php:49 0.0480 1211736 3. Joomla\CMS\Application\SiteApplication->doExecute() /var/www/astarmathsandphysics/libraries/src/Application/CMSApplication.php:267 0.1195 4192824 4. Joomla\CMS\Application\SiteApplication->dispatch() /var/www/astarmathsandphysics/libraries/src/Application/SiteApplication.php:233 0.1224 4220360 5. Joomla\CMS\Component\ComponentHelper::renderComponent() /var/www/astarmathsandphysics/libraries/src/Application/SiteApplication.php:194 0.1232 4238072 6. Joomla\CMS\Component\ComponentHelper::executeComponent() /var/www/astarmathsandphysics/libraries/src/Component/ComponentHelper.php:356 0.1235 4268592 7. require_once('/var/www/astarmathsandphysics/components/com_content/content.php') /var/www/astarmathsandphysics/libraries/src/Component/ComponentHelper.php:381 0.1246 4291312 8. ContentController->execute() /var/www/astarmathsandphysics/components/com_content/content.php:42 0.1246 4291312 9. ContentController->display() /var/www/astarmathsandphysics/libraries/src/MVC/Controller/BaseController.php:710 0.1749 4968896 10. ContentController->display() /var/www/astarmathsandphysics/components/com_content/controller.php:113 0.1787 5161048 11. Joomla\CMS\Cache\Controller\ViewController->get() /var/www/astarmathsandphysics/libraries/src/MVC/Controller/BaseController.php:663 0.1792 5181976 12. ContentViewArticle->display() /var/www/astarmathsandphysics/libraries/src/Cache/Controller/ViewController.php:102 0.1906 5378672 13. Joomla\CMS\Plugin\PluginHelper::importPlugin() /var/www/astarmathsandphysics/components/com_content/views/article/view.html.php:189 0.1906 5378928 14. Joomla\CMS\Plugin\PluginHelper::import() /var/www/astarmathsandphysics/libraries/src/Plugin/PluginHelper.php:182

Djikstra's Algorithm

Dijkstra’s algorithm is used to find the shortest path tree from a given node to any (or every) other node in a network.

Dijkstra’s algorithm requires that each node in the network be assigned values (labels). The labels are assigned in order of distance from the starting point, with the labels assigned as we work our way through the network. There is a working label and a permanent label, as well as an ordering label. The smallest working label ateach iteration will become permanent.

The steps of Dijkstra’s algorithm are:

  1. Give the start point the permanent label of 0.

  2. Any vertex directly connected to the last vertex given a permanent label is assigned a working value equal to the weight of the connecting edge added to the permanent value of the node you are coming from. If it already has a working value replace it only if the new working value is lower.

  3. Select the minimum current working value in the network and make it the permanent value for that node.

  4. If the destination node has a permanent label go to step 5, otherwise go to step 2.

  5. Connect the destination to the start, working backwards. Select any edge for which the difference between the permanent labels at each end is equal to the weight of the edge.

In this example we will consider the network in the diagram below. We would like to find the shortest path from node A to node F.

It is a good idea to use a system for keeping track of the current working labels and the ordering and permanent labels of each of thenodes in the network. A small grid is drawn near each of the nodes, working labels are written in the lower box, ordering labels in the upper right box.

Node A is labelled 0. The distance from A to A is 0. The closest to A is B, distance 4 from A, so B is labelled 1.

C and D are directly connected to B. The working value is of D is 4+6=10 and the working calue of C is 4+9=13. A lesser distance 5 from A exists for C, and this becomes the permanent value. Node C has label 2.

E and G are directly connected to C. The closest to C is E, distance 6 from A. E is labelled 3.

E is connected to F.

By inspection all the distances are minimised and we can label the remaining nodes.