{"id":198382,"date":"2024-10-27T16:25:47","date_gmt":"2024-10-27T21:25:47","guid":{"rendered":"https:\/\/lifeboat.com\/blog\/2024\/10\/computer-scientists-establish-the-best-way-to-traverse-a-graph"},"modified":"2024-10-27T16:25:47","modified_gmt":"2024-10-27T21:25:47","slug":"computer-scientists-establish-the-best-way-to-traverse-a-graph","status":"publish","type":"post","link":"https:\/\/lifeboat.com\/blog\/2024\/10\/computer-scientists-establish-the-best-way-to-traverse-a-graph","title":{"rendered":"Computer Scientists Establish the Best Way to Traverse a Graph"},"content":{"rendered":"<p><a class=\"aligncenter blog-photo\" href=\"https:\/\/lifeboat.com\/blog.images\/computer-scientists-establish-the-best-way-to-traverse-a-graph2.jpg\"><\/a><\/p>\n<p>A new proof shows that an upgraded version of the 70-year-old Dijkstra\u2019s algorithm reigns supreme: It finds the most efficient pathways through any graph.<\/p>\n<p>It doesn\u2019t just tell you the fastest route to one destination.<\/p>\n<hr>\n<p>In an interview toward the end of his life, Dijkstra credited his algorithm\u2019s enduring appeal in part to its unusual origin story. \u201cWithout pencil and paper you are almost forced to avoid all avoidable complexities,\u201d he said.<\/p>\n<p>Dijkstra\u2019s algorithm doesn\u2019t just tell you the fastest route to one destination. Instead, it gives you an ordered list of travel times from your current location to every other point that you might want to visit \u2014 a solution to what researchers call the single-source shortest-paths problem. The algorithm works in an abstracted road map called a graph: a network of interconnected points (called vertices) in which the links between vertices are labeled with numbers (called weights). These weights might represent the time required to traverse each road in a network, and they can change depending on traffic patterns. The larger a weight, the longer it takes to traverse that path.<\/p>\n<p>To get a sense of Dijkstra\u2019s algorithm, imagine yourself wandering through a graph, writing down the travel time from your starting point to each new vertex on a piece of scratch paper. Whenever you have a choice about which direction to explore next, head toward the closest vertex you haven\u2019t visited yet. If you discover a faster route to any vertex, jot down the new time and cross out the old one. When you\u2019re sure that you\u2019ve found the fastest path, move the travel time from your notes to a separate, more presentable list.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>A new proof shows that an upgraded version of the 70-year-old Dijkstra\u2019s algorithm reigns supreme: It finds the most efficient pathways through any graph. It doesn\u2019t just tell you the fastest route to one destination. In an interview toward the end of his life, Dijkstra credited his algorithm\u2019s enduring appeal in part to its unusual [\u2026]<\/p>\n","protected":false},"author":709,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1523,41],"tags":[],"class_list":["post-198382","post","type-post","status-publish","format-standard","hentry","category-computing","category-information-science"],"_links":{"self":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/198382","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/users\/709"}],"replies":[{"embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/comments?post=198382"}],"version-history":[{"count":0,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/posts\/198382\/revisions"}],"wp:attachment":[{"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/media?parent=198382"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/categories?post=198382"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lifeboat.com\/blog\/wp-json\/wp\/v2\/tags?post=198382"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}