Close Menu
Best in TechnologyBest in Technology
  • News
  • Phones
  • Laptops
  • Gadgets
  • Gaming
  • AI
  • Tips
  • More
    • Web Stories
    • Global
    • Press Release

Subscribe to Updates

Get the latest tech news and updates directly to your inbox.

What's On

Trump and the Energy Industry Are Eager to Power AI With Fossil Fuels

16 July 2025

“Think Gaming, Think Infinix”: CEO Anish Kapoor on Infinix’s Mission to Democratise Mobile Gaming in India

16 July 2025

Dyneema’s New Fiber Composite Is Lighter, Stronger, and More Durable Than Ever

16 July 2025
Facebook X (Twitter) Instagram
Just In
  • Trump and the Energy Industry Are Eager to Power AI With Fossil Fuels
  • “Think Gaming, Think Infinix”: CEO Anish Kapoor on Infinix’s Mission to Democratise Mobile Gaming in India
  • Dyneema’s New Fiber Composite Is Lighter, Stronger, and More Durable Than Ever
  • Vivo Y400 5G Could Launch in India in August; Price and Colour Options Tipped
  • Can US Measles Outbreaks Be Stopped?
  • iPhone 17 Pro, iPhone 17 Pro Max Could Ditch Titanium for Aluminium Frame
  • Cyberpunk 2077 Update 2.3 Brings New Quests, Vehicles, VRR Support, And More Tomorrow
  • Review: ElliQ AI Companion Robot
Facebook X (Twitter) Instagram Pinterest Vimeo
Best in TechnologyBest in Technology
  • News
  • Phones
  • Laptops
  • Gadgets
  • Gaming
  • AI
  • Tips
  • More
    • Web Stories
    • Global
    • Press Release
Subscribe
Best in TechnologyBest in Technology
Home » Scientists Establish the Best Algorithm for Traversing a Map
News

Scientists Establish the Best Algorithm for Traversing a Map

News RoomBy News Room17 November 20243 Mins Read
Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
Share
Facebook Twitter LinkedIn Pinterest Email

“It’s a great algorithm,” said Erik Demaine, a computer scientist at the Massachusetts Institute of Technology. “It’s very fast, simple, and easy to implement.”

To put this procedure into practice, you’d need to decide on a system for organizing your notes—a data structure, in the lingo of computer science. That may sound like a minor technical detail, but time spent searching through your notes whenever you need to edit or remove an entry can have a big effect on the overall runtime of the algorithm.

Dijkstra’s paper used a simple data structure that left room for improvement. In the following decades, researchers developed better ones, affectionately dubbed “heaps,” in which certain items are easier to find than others. They take advantage of the fact that Dijkstra’s algorithm only ever needs to remove the entry for the closest remaining vertex. “A heap is basically a data structure that allows you to do this very quickly,” said Václav Rozhoň, a researcher at the Institute for Computer Science, Artificial Intelligence and Technology (INSAIT) in Sofia, Bulgaria.

In 1984, two computer scientists developed a clever heap design that enabled Dijkstra’s algorithm to reach a theoretical limit, or “lower bound,” on the time required to solve the single-source shortest-paths problem. In one specific sense, this version of Dijkstra’s algorithm is the best possible. That was the last word on the standard version of the problem for nearly 40 years. Things only changed when a few researchers took a closer look at what it means to be “best.”

Best Behavior

Researchers typically compare algorithms by studying how they fare in worst-case scenarios. Imagine the world’s most confusing street grid, then add some especially perplexing traffic patterns. If you insist on finding the fastest routes in these extreme circumstances, the 1984 version of Dijkstra’s algorithm is provably unbeatable.

But hopefully, your city doesn’t have the world’s worst street grid. And so you may ask: Is there an algorithm that’s unbeatable on every road network? The first step to answering this question is to make the conservative assumption that each network has worst-case traffic patterns. Then you want your algorithm to find the fastest paths through any possible graph layout, assuming the worst possible weights. Researchers call this condition “universal optimality.” If you had a universally optimal algorithm for the simpler problem of just getting from one point on a graph to another, it could help you beat rush hour traffic in every city in the world.

Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
Previous ArticleWatch Yellowstone season 5, episode 10: release date, time, channel, and plot
Next Article The Onyx Boox Palma 2 is the gadget I didn’t know I wanted

Related Articles

News

Trump and the Energy Industry Are Eager to Power AI With Fossil Fuels

16 July 2025
News

Dyneema’s New Fiber Composite Is Lighter, Stronger, and More Durable Than Ever

16 July 2025
News

Can US Measles Outbreaks Be Stopped?

16 July 2025
News

Review: ElliQ AI Companion Robot

16 July 2025
News

DHS Faces New Pressure Over DNA Taken From Immigrant Children

16 July 2025
News

Adoption Agency Data Exposure Revealed Information About Children and Parents

16 July 2025
Demo
Top Articles

ChatGPT o1 vs. o1-mini vs. 4o: Which should you use?

15 December 2024101 Views

Costco partners with Electric Era to bring back EV charging in the U.S.

28 October 202495 Views

Oppo Reno 14, Reno 14 Pro India Launch Timeline and Colourways Leaked

27 May 202582 Views

Subscribe to Updates

Get the latest tech news and updates directly to your inbox.

Latest News
Phones

iPhone 17 Pro, iPhone 17 Pro Max Could Ditch Titanium for Aluminium Frame

News Room16 July 2025
Gaming

Cyberpunk 2077 Update 2.3 Brings New Quests, Vehicles, VRR Support, And More Tomorrow

News Room16 July 2025
News

Review: ElliQ AI Companion Robot

News Room16 July 2025
Most Popular

The Spectacular Burnout of a Solar Panel Salesman

13 January 2025124 Views

ChatGPT o1 vs. o1-mini vs. 4o: Which should you use?

15 December 2024101 Views

Costco partners with Electric Era to bring back EV charging in the U.S.

28 October 202495 Views
Our Picks

Vivo Y400 5G Could Launch in India in August; Price and Colour Options Tipped

16 July 2025

Can US Measles Outbreaks Be Stopped?

16 July 2025

iPhone 17 Pro, iPhone 17 Pro Max Could Ditch Titanium for Aluminium Frame

16 July 2025

Subscribe to Updates

Get the latest tech news and updates directly to your inbox.

Facebook X (Twitter) Instagram Pinterest
  • Privacy Policy
  • Terms of use
  • Advertise
  • Contact Us
© 2025 Best in Technology. All Rights Reserved.

Type above and press Enter to search. Press Esc to cancel.