{"id":87,"date":"2021-03-31T02:04:37","date_gmt":"2021-03-31T02:04:37","guid":{"rendered":"http:\/\/learnlearn.uk\/algorithms\/?page_id=87"},"modified":"2021-06-11T02:09:55","modified_gmt":"2021-06-11T02:09:55","slug":"pathfinding-algorithms","status":"publish","type":"page","link":"https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/","title":{"rendered":"Pathfinding Algorithms"},"content":{"rendered":"<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Starter<\/h2>\n<div class=\"tabcontent\">\n\n<h3>Starter<\/h3>\n<p>Today we are going to be exploring different algorithms for finding the shortest path between two points.<\/p>\n<p>To start have a look at the interactive game in the link provided. How do the different algorithms behave?<\/p>\n<p>How does Dijkstra&#8217;s work?<\/p>\n<a href='https:\/\/qiao.github.io\/PathFinding.js\/visual\/' class='arconix-button arconix-button-medium arconix-button-gray'>Click here for the pathfinding visualisation<\/a>\n<p>&nbsp;<\/p>\n\n<\/div><h2 class=\"tabtitle\">Videos<\/h2>\n<div class=\"tabcontent\">\n\n<h3>Dijkstra&#8217;s Algorithm &#8211; Videos<\/h3>\n<p><strong>Introduction 1<\/strong><\/p>\n<div class=\"nv-iframe-embed\">\n<div class=\"container-lazyload preview-lazyload container-youtube js-lazyload--not-loaded\"><a href=\"https:\/\/www.youtube.com\/watch?v=pVfj6mxhdMw\" class=\"lazy-load-youtube preview-lazyload preview-youtube\" data-video-title=\"Graph Data Structure 4. Dijkstra\u2019s Shortest Path Algorithm\" title=\"Play video &quot;Graph Data Structure 4. Dijkstra\u2019s Shortest Path Algorithm&quot;\">https:\/\/www.youtube.com\/watch?v=pVfj6mxhdMw<\/a><noscript>Video can&#8217;t be loaded because JavaScript is disabled: <a href=\"https:\/\/www.youtube.com\/watch?v=pVfj6mxhdMw\" title=\"Graph Data Structure 4. Dijkstra\u2019s Shortest Path Algorithm\">Graph Data Structure 4. Dijkstra\u2019s Shortest Path Algorithm (https:\/\/www.youtube.com\/watch?v=pVfj6mxhdMw)<\/a><\/noscript><\/div>\n<\/div>\n<p><strong>Introduction 2<\/strong><\/p>\n<div class=\"nv-iframe-embed\">\n<div class=\"container-lazyload preview-lazyload container-youtube js-lazyload--not-loaded\"><a href=\"https:\/\/www.youtube.com\/watch?v=GazC3A4OQTE\" class=\"lazy-load-youtube preview-lazyload preview-youtube\" data-video-title=\"Dijkstra&#039;s Algorithm - Computerphile\" title=\"Play video &quot;Dijkstra&#039;s Algorithm - Computerphile&quot;\">https:\/\/www.youtube.com\/watch?v=GazC3A4OQTE<\/a><noscript>Video can&#8217;t be loaded because JavaScript is disabled: <a href=\"https:\/\/www.youtube.com\/watch?v=GazC3A4OQTE\" title=\"Dijkstra&#039;s Algorithm - Computerphile\">Dijkstra&#039;s Algorithm &#8211; Computerphile (https:\/\/www.youtube.com\/watch?v=GazC3A4OQTE)<\/a><\/noscript><\/div>\n<\/div>\n<p>&nbsp;<\/p>\n\n<\/div><h2 class=\"tabtitle\">Limitations<\/h2>\n<div class=\"tabcontent\">\n\n<h3>Limitations of Dijkstra&#8217;s Algorithm<\/h3>\n<p>Dijkstra&#8217;s algorithm is a great, simple way of finding the shortest path in most situations, however it does have 2 big weaknesses<\/p>\n<p><strong>A lack of heuristics<\/strong><\/p>\n<p>Dijkstra&#8217;s algorithm has no notion of the overall shortest direction to the end goal, so it will actually spend a lot of time searching in completely the wrong direction if the routes in the wrong direction are shorter than the route in the correct direction. It will find the shortest route in the end but it will waste a lot of time.<\/p>\n<p>In small networks this isn&#8217;t a problem but when you have massive networks (like road networks or the internet) then it will result in massive inefficiencies.<\/p>\n<p><strong>Negative Weighted Costs<\/strong><\/p>\n<p>On physical networks with physical distances you can&#8217;t have negative weights, but one some networks where you are calculating costs you might have negative costs for a particular leg. Dijkstra&#8217;s cant handle these negative costs.<\/p>\n<p><strong>Directed networks<\/strong><\/p>\n<p>Dijkstra&#8217;s algorithm doesn&#8217;t always work best when there are directed networks (such as motorways that only run in one direction)<\/p>\n<p>&nbsp;<\/p>\n\n<\/div><h2 class=\"tabtitle\">Internet Routing<\/h2>\n<div class=\"tabcontent\">\n\n<h3>Internal Routing with Shortest Path<\/h3>\n<div class=\"nv-iframe-embed\">\n<div class=\"container-lazyload preview-lazyload container-youtube js-lazyload--not-loaded\"><a href=\"https:\/\/www.youtube.com\/watch?v=AkxqkoxErRk\" class=\"lazy-load-youtube preview-lazyload preview-youtube\" data-video-title=\"Routers, The Internet &amp; YouTube Offline - Computerphile\" title=\"Play video &quot;Routers, The Internet &amp; YouTube Offline - Computerphile&quot;\">https:\/\/www.youtube.com\/watch?v=AkxqkoxErRk<\/a><noscript>Video can&#8217;t be loaded because JavaScript is disabled: <a href=\"https:\/\/www.youtube.com\/watch?v=AkxqkoxErRk\" title=\"Routers, The Internet &amp; YouTube Offline - Computerphile\">Routers, The Internet &amp; YouTube Offline &#8211; Computerphile (https:\/\/www.youtube.com\/watch?v=AkxqkoxErRk)<\/a><\/noscript><\/div>\n<\/div>\n\n<\/div><h2 class=\"tabtitle\">Resources<\/h2>\n<div class=\"tabcontent\">\n\n<h3>Resources<\/h3>\n<p><a href=\"https:\/\/docs.google.com\/presentation\/d\/19jV-Q6JMn5qWjWkIP2NkWadDKmOxnK1xwVKDbkgfvgw\/edit?usp=sharing\">Teacher Presentation<\/a><\/p>\n<p><a href=\"https:\/\/docs.google.com\/spreadsheets\/d\/1shYYQfV32GDDO1988-OuketGf92zKOq-eEQJ0tJdtvA\/edit?usp=sharing\">Example Work-through Google Sheet<\/a><\/p>\n<p><strong>Worksheets<\/strong><\/p>\n<p><a href=\"https:\/\/www.tes.com\/teaching-resource\/dijkstra-s-algorithm-6147438\">https:\/\/www.tes.com\/teaching-resource\/dijkstra-s-algorithm-6147438<\/a><\/p>\n<p><a href=\"https:\/\/courses.cs.washington.edu\/courses\/cse373\/13au\/lecture15.pdf\">https:\/\/courses.cs.washington.edu\/courses\/cse373\/13au\/lecture15.pdf<\/a><\/p>\n<p><a href=\"https:\/\/courses.cs.washington.edu\/courses\/cse373\/13au\/midterm2Unsolved.pdf\">https:\/\/courses.cs.washington.edu\/courses\/cse373\/13au\/midterm2Unsolved.pdf\u00a0<\/a> \u00a0(page\u00a0 9 negative costs question)<\/p>\n<p>&nbsp;<\/p>\n<p><a href=\"https:\/\/www.pearsonschoolsandfecolleges.co.uk\/secondary\/Mathematics\/16plus\/AdvancingMathsForAQA2ndEdition\/Samples\/SampleMaterial\/Chp-02%20023-043.pdf\">https:\/\/www.pearsonschoolsandfecolleges.co.uk\/secondary\/Mathematics\/16plus\/AdvancingMathsForAQA2ndEdition\/Samples\/SampleMaterial\/Chp-02%20023-043.pdf<\/a><\/p>\n<h3>Programming Challenge<\/h3>\n<p>This challenge is only for experienced Python programmers!<\/p>\n<p>Using Python program an implementation of Dijkstra&#8217;s algorithm to find the shortest driving distance between two cities using the data provided.<\/p>\n<p><a href=\"https:\/\/docs.google.com\/presentation\/d\/1XsiT-S52r3nynwbyHWmllC0qJEDwZc4vVrny-jCdBMg\/edit?usp=sharing\">UK Road Graph<\/a><\/p>\n<p><a href=\"https:\/\/docs.google.com\/spreadsheets\/d\/1TkepnlihTGv9Y7vCwOGqlDWSwQzfMdo-5S5OPuJUJFs\/edit?usp=sharing\">UK Road Sheets File (Download as CSV to use within your program)<\/a><\/p>\n<p><a href=\"https:\/\/docs.google.com\/spreadsheets\/d\/1RgzQkykOIjP0ebhrb3VJifAx4q6OsZ3BEXDn_W1fjbw\/edit#gid=0\">UK Roads Matrix<\/a><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<\/div><\/div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Starter Today we are going to be exploring different algorithms for finding the shortest path between two points. To start have a look at the interactive game in the link provided. How do the different algorithms behave? How does Dijkstra&#8217;s work? &nbsp; Dijkstra&#8217;s Algorithm &#8211; Videos Introduction 1 https:\/\/www.youtube.com\/watch?v=pVfj6mxhdMwVideo can&#8217;t be loaded because JavaScript is&hellip;&nbsp;<a href=\"https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/\" class=\"\" rel=\"bookmark\">Read More &raquo;<span class=\"screen-reader-text\">Pathfinding Algorithms<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"neve_meta_sidebar":"","neve_meta_container":"","neve_meta_enable_content_width":"","neve_meta_content_width":70,"neve_meta_title_alignment":"","neve_meta_author_avatar":"","neve_post_elements_order":"","neve_meta_disable_header":"","neve_meta_disable_footer":"","neve_meta_disable_title":""},"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v20.6 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Pathfinding Algorithms - Algorithms<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/\" \/>\n<meta property=\"og:locale\" content=\"en_GB\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Pathfinding Algorithms - Algorithms\" \/>\n<meta property=\"og:description\" content=\"Starter Today we are going to be exploring different algorithms for finding the shortest path between two points. To start have a look at the interactive game in the link provided. How do the different algorithms behave? How does Dijkstra&#8217;s work? &nbsp; Dijkstra&#8217;s Algorithm &#8211; Videos Introduction 1 https:\/\/www.youtube.com\/watch?v=pVfj6mxhdMwVideo can&#8217;t be loaded because JavaScript is&hellip;&nbsp;Read More &raquo;Pathfinding Algorithms\" \/>\n<meta property=\"og:url\" content=\"https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/\" \/>\n<meta property=\"og:site_name\" content=\"Algorithms\" \/>\n<meta property=\"article:modified_time\" content=\"2021-06-11T02:09:55+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Estimated reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/\",\"url\":\"https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/\",\"name\":\"Pathfinding Algorithms - Algorithms\",\"isPartOf\":{\"@id\":\"https:\/\/learnlearn.uk\/algorithms\/#website\"},\"datePublished\":\"2021-03-31T02:04:37+00:00\",\"dateModified\":\"2021-06-11T02:09:55+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/#breadcrumb\"},\"inLanguage\":\"en-GB\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"KS3 Algorithms Unit\",\"item\":\"https:\/\/learnlearn.uk\/algorithms\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Pathfinding Algorithms\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/learnlearn.uk\/algorithms\/#website\",\"url\":\"https:\/\/learnlearn.uk\/algorithms\/\",\"name\":\"Algorithms\",\"description\":\"An intro\",\"publisher\":{\"@id\":\"https:\/\/learnlearn.uk\/algorithms\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/learnlearn.uk\/algorithms\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-GB\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/learnlearn.uk\/algorithms\/#organization\",\"name\":\"Algorithms\",\"url\":\"https:\/\/learnlearn.uk\/algorithms\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-GB\",\"@id\":\"https:\/\/learnlearn.uk\/algorithms\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/learnlearn.uk\/algorithms\/wp-content\/uploads\/sites\/12\/2021\/04\/LearnLearnLogowhite.png\",\"contentUrl\":\"https:\/\/learnlearn.uk\/algorithms\/wp-content\/uploads\/sites\/12\/2021\/04\/LearnLearnLogowhite.png\",\"width\":710,\"height\":98,\"caption\":\"Algorithms\"},\"image\":{\"@id\":\"https:\/\/learnlearn.uk\/algorithms\/#\/schema\/logo\/image\/\"}}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Pathfinding Algorithms - Algorithms","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/","og_locale":"en_GB","og_type":"article","og_title":"Pathfinding Algorithms - Algorithms","og_description":"Starter Today we are going to be exploring different algorithms for finding the shortest path between two points. To start have a look at the interactive game in the link provided. How do the different algorithms behave? How does Dijkstra&#8217;s work? &nbsp; Dijkstra&#8217;s Algorithm &#8211; Videos Introduction 1 https:\/\/www.youtube.com\/watch?v=pVfj6mxhdMwVideo can&#8217;t be loaded because JavaScript is&hellip;&nbsp;Read More &raquo;Pathfinding Algorithms","og_url":"https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/","og_site_name":"Algorithms","article_modified_time":"2021-06-11T02:09:55+00:00","twitter_card":"summary_large_image","twitter_misc":{"Estimated reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/","url":"https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/","name":"Pathfinding Algorithms - Algorithms","isPartOf":{"@id":"https:\/\/learnlearn.uk\/algorithms\/#website"},"datePublished":"2021-03-31T02:04:37+00:00","dateModified":"2021-06-11T02:09:55+00:00","breadcrumb":{"@id":"https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/#breadcrumb"},"inLanguage":"en-GB","potentialAction":[{"@type":"ReadAction","target":["https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/learnlearn.uk\/algorithms\/pathfinding-algorithms\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"KS3 Algorithms Unit","item":"https:\/\/learnlearn.uk\/algorithms\/"},{"@type":"ListItem","position":2,"name":"Pathfinding Algorithms"}]},{"@type":"WebSite","@id":"https:\/\/learnlearn.uk\/algorithms\/#website","url":"https:\/\/learnlearn.uk\/algorithms\/","name":"Algorithms","description":"An intro","publisher":{"@id":"https:\/\/learnlearn.uk\/algorithms\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/learnlearn.uk\/algorithms\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-GB"},{"@type":"Organization","@id":"https:\/\/learnlearn.uk\/algorithms\/#organization","name":"Algorithms","url":"https:\/\/learnlearn.uk\/algorithms\/","logo":{"@type":"ImageObject","inLanguage":"en-GB","@id":"https:\/\/learnlearn.uk\/algorithms\/#\/schema\/logo\/image\/","url":"https:\/\/learnlearn.uk\/algorithms\/wp-content\/uploads\/sites\/12\/2021\/04\/LearnLearnLogowhite.png","contentUrl":"https:\/\/learnlearn.uk\/algorithms\/wp-content\/uploads\/sites\/12\/2021\/04\/LearnLearnLogowhite.png","width":710,"height":98,"caption":"Algorithms"},"image":{"@id":"https:\/\/learnlearn.uk\/algorithms\/#\/schema\/logo\/image\/"}}]}},"rttpg_featured_image_url":null,"rttpg_author":{"display_name":"learnlearnadmin","author_link":"https:\/\/learnlearn.uk\/algorithms\/author\/learnlearnadmin\/"},"rttpg_comment":0,"rttpg_category":null,"rttpg_excerpt":"Starter Today we are going to be exploring different algorithms for finding the shortest path between two points. To start have a look at the interactive game in the link provided. How do the different algorithms behave? How does Dijkstra&#8217;s work? &nbsp; Dijkstra&#8217;s Algorithm &#8211; Videos Introduction 1 https:\/\/www.youtube.com\/watch?v=pVfj6mxhdMwVideo can&#8217;t be loaded because JavaScript is&hellip;&nbsp;Read&hellip;","_links":{"self":[{"href":"https:\/\/learnlearn.uk\/algorithms\/wp-json\/wp\/v2\/pages\/87"}],"collection":[{"href":"https:\/\/learnlearn.uk\/algorithms\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/learnlearn.uk\/algorithms\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/learnlearn.uk\/algorithms\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/learnlearn.uk\/algorithms\/wp-json\/wp\/v2\/comments?post=87"}],"version-history":[{"count":9,"href":"https:\/\/learnlearn.uk\/algorithms\/wp-json\/wp\/v2\/pages\/87\/revisions"}],"predecessor-version":[{"id":203,"href":"https:\/\/learnlearn.uk\/algorithms\/wp-json\/wp\/v2\/pages\/87\/revisions\/203"}],"wp:attachment":[{"href":"https:\/\/learnlearn.uk\/algorithms\/wp-json\/wp\/v2\/media?parent=87"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}