Finally, a Fast Algorithm for Shortest Paths on Negative Graphs | Quanta Magazine

In algorithms, as in life, negativity can be a drag.

Consider the problem of finding the shortest path between two points on a graph — a network of nodes connected by links, or edges. Often, these edges aren’t interchangeable: A graph could represent a road map on which some roads are slower than others or have higher tolls. Computer scientists account for these differences by pairing each edge with a “weight” that quantifies the cost of moving across that segment — whether that cost represents time, money or something else. Since the 1950s, they’ve known how to find shortest paths essentially as fast as theoretically possible, assuming all weights are positive numbers.

But on some graphs weights can be negative — traveling along one segment can offset the cost of traversing another. Consider, for instance, a delivery driver who must balance the cost of gas and tolls (represented by positive weights) against income from transporting packages (represented by negative weights). In such cases, the fastest known shortest-path algorithm doesn’t work. For decades, fast algorithms for finding shortest paths on negative-weight graphs have remained elusive.

Now a trio of computer scientists has solved this long-standing problem. Their new algorithm, which finds the shortest paths through a graph from a given “source” node to every other node, nearly matches the speed that positive-weight algorithms achieved so long ago.

What’s more, the new approach uses decades-old mathematical techniques, eschewing more sophisticated methods that have dominated modern graph theory research.

“I just couldn’t believe such a simple algorithm exists,” said Maximilian Probst Gutenberg, a computer scientist at the Swiss Federal Institute of Technology Zurich. “All of it has been there for 40 years. It just took someone to be really clever and determined to make it all work.”

The Limits of Greed

The story begins in 1956, when the Dutch computer scientist Edsger Dijkstra developed a fast algorithm to find shortest paths on a graph with only positive weights. To understand it, imagine starting from the source and exploring the graph one node at a time, jotting down the weights of newly discovered edges as you go. Each time you visit a node, make preliminary estimates of the shortest paths from the source to each of the new node’s neighbors, updating any existing estimates if you’ve found a new shorter path. To decide which unexplored node to visit next, use what’s called a greedy strategy: Go to whichever is closest to the source according to your current estimate.

With positive weights, the path that Dijkstra’s algorithm takes to visit each node for the first time is truly the shortest. It’s easiest to see that this is true for the very first step. Imagine two nodes A and B connected by an edge with weight 2. If A is the source node, and every other edge touching it has a larger weight, then the direct path from A to B must be the shortest possible path connecting those two points, since the first segment of any other path would already be longer. Similar reasoning works at each step. The algorithm never has to look back, so it’s guaranteed to finish after running through the graph once — that’s what makes it so fast.

But negative weights spell trouble for Dijkstra’s greedy strategy. Consider again our delivery driver. A direct route from A to B that nets a small profit may earn less money than a circuitous path that has a big payoff somewhere. “You can’t make decisions just based on the local information,” said Sanjeev Khanna, a computer scientist at the University of Pennsylvania. “You may have to make several seemingly suboptimal moves to finally get a real reward.”

For decades, computer scientists working on negative-weight graphs tried to match the speed of Dijkstra’s algorithm with similar “combinatorial” algorithms. These involve discrete operations — like counting possibilities, modifying weights and selectively deleting edges — that reflect the discrete structure of the underlying graph. Progress slowed by the 1990s, however. More recently, researchers have used “continuous optimization” algorithms, which borrow tricks from calculus. Unfortunately, the resulting speedups have been limited, and have often come at the cost of simplicity.

Break the Cycle

In the summer of 2021, two computer scientists who’d become colleagues at the University of Copenhagen — Danupon Nanongkai and Christian Wulff-Nilsen — were searching for a topic for a joint research project. “Christian said, ‘Oh, by the way, I was on vacation, and because of that I was trying to think of something very ambitious,’” recalled Nanongkai, who’s now at the Max Planck Institute for Informatics in Saarbrucken, Germany. They settled on the negative-weight shortest-paths problem and invited Aaron Bernstein of Rutgers University to join them.

All three researchers were experts in combinatorial graph algorithms for other problems, and they wanted to see how far these relatively ancient approaches could get them. “There’s actually a certain freedom in working on a problem that’s ambitious and has been open for a long time,” Bernstein said.

The trio started by temporarily ignoring a subset of possible graphs: those containing negative cycles. These are paths that loop back to where they started after passing through a series of edges whose weights add up to a negative number. In a graph with negative cycles reachable from the starting point, the notion of a shortest path breaks down, since you can make the distance to any node as negative (or as profitable) as you like, by taking repeated laps around the negative cycle before heading off to your destination.

The researchers suspected that long negative paths were mainly responsible for making the problem difficult. So they began to focus on tight clusters of nearby nodes, which can’t contain any long negative paths: That’s because if two points are connected by a short positive path, adding a long negative path between them would create a negative cycle. Within a tight cluster, “the fact that everyone is close together in a positive sense actually gives you useful information about the negative edges as well,” Bernstein said. “It tells you things can’t be too negative.”

Most graphs contain many such tight-knit clusters that are only weakly connected to each other. If the researchers could pinpoint all the clusters, they suspected they could develop a way to find shortest paths quickly within each one. From there, they might have an easier time connecting individual clusters and finding the shortest paths on the original graph. But that would require quickly spotting the regions of any graph in which nodes are close together — something they didn’t know how to do. The key turned out to be a technique that originated in an entirely different branch of graph theory.

Cutting Up Graphs  

In the 1980s, computer scientists developed a technique called low-diameter decomposition to pick out tight clusters in a graph and identify the edges to delete to separate those clusters. This technique provides a way to divide graphs into independent sections. It was invented to facilitate “distributed” algorithms, in which computations run in parallel on different parts of a graph, so it was less obviously useful for shortest-paths algorithms, which don’t have this property.

Bernstein, Nanongkai and Wulff-Nilsen realized that low-diameter decomposition could help them identify clusters without much concentrated negativity. Unfortunately, standard low-diameter decomposition algorithms only work on undirected graphs — those in which every edge can be traversed in both directions. The negative-weight shortest-paths problem, meanwhile, only makes sense on directed graphs, in which every edge is a one-way street. (Otherwise, a single undirected negative edge would create a negative cycle consisting of repeated hops back and forth across that edge.) If the researchers wanted to use low-diameter decomposition, they’d have to adapt it.

That’s what they did in their new paper. Inspired by past work in which Bernstein and Wulff-Nilsen had collaborated with Probst Gutenberg, they developed a fracturing procedure for directed graphs analogous to low-diameter decomposition. The procedure chops up an arbitrary directed graph into a series of tight-knit clusters by using a random process to delete just a handful of edges. Afterward, those clusters are connected by a sparser network in which all the edges point in the same direction. That kind of network is called a directed acyclic graph, or DAG.

Think of a DAG like a stream in which water may flow down different paths: Some paths flow in from different sources, others fan out in different directions, and still others may split apart and merge back together. But nothing ever flows backward, so there are no cycles; this makes DAGs much easier to work with.

Researchers have long known how to rapidly find shortest paths on DAGs even with negative weights. So the fracturing technique enabled the three researchers to reduce any directed graph to a combination of two special cases — DAGs and tight clusters — that were each easy to handle.

The new shortest-paths algorithm repeatedly uses the fracturing procedure to break a graph into tight-knit clusters connected by a DAG. It then breaks those clusters apart further and further. At the end of the process, the clusters at the innermost level are as closely connected as possible. Part of the reason the algorithm is so fast is that it doesn’t take many iterations to fully break down even a very large graph, just as it doesn’t take long to cut a large number down to a reasonable size if you repeatedly divide it in half.

With the graph fully broken down in this manner, the researchers could quickly find shortest paths through every part of the graph. For the tight clusters at the innermost level of the nested graph structure, this was easy — they had practically no negativity left. And the researchers already knew how to find shortest paths on the DAG sections joining them.

Finally, the algorithm adds back the edges eliminated by the fracturing process and calculates their effects on the shortest paths. The researchers proved that their process for randomly deleting edges would almost always require just a few deletions to eliminate “backward” edges — the kind that would turn their DAG into a graph with large cycles. That made it extremely unlikely that any shortest path would pass through too many such backward segments, so they could solve this tricky final step by combining two textbook methods from the 1950s: Dijkstra’s algorithm and the first algorithm developed for negative-weight graphs.

“It’s an extremely clever composition of these ideas,” Khanna said. The algorithm is the first for negative-weight graphs that runs in “near-linear” time — which means its runtime is nearly proportional to the time required just to count all the edges, the fastest it could possibly be.

And what of the graphs with negative cycles, which the researchers decided to ignore at the start? After putting the finishing touches on their shortest-paths algorithm, they showed that it could also work as a fast algorithm for pinpointing negative cycles. Virtually no graph was beyond its reach.

Parallel Paths

Bernstein presented the team’s result at the 2022 Foundations of Computer Science conference, where their manuscript describing the new algorithm was deemed one of two best papers. The other paper also happened to describe a new near-linear-time algorithm for solving a long-standing problem in graph theory.

That algorithm, developed by Probst Gutenberg and five other researchers, addressed a more general problem called minimum-cost flow, in which the goal is to optimize transport through many paths in parallel, and each edge has a maximum capacity as well as an associated cost. Shortest-paths problems are a special case of minimum-cost flow, so the new minimum-cost-flow algorithm could also be used to solve the negative-weight shortest-paths problem in near-linear time, albeit with a radically different approach.

The team working on minimum-cost flow developed their general-purpose fast algorithm using an intricate synthesis of combinatorial and continuous optimization techniques that makes it unwieldy in practice, at least currently. The combinatorial algorithm by Bernstein and his colleagues, though restricted to a more specific problem, achieves its near-linear runtime without sacrificing simplicity.

“This is what’s so astonishing about this paper,” said Probst Gutenberg. “You can explain it to an undergraduate student, and you can also implement it on your computer.”

As a result, this new algorithm has revived interest in combinatorial approaches to other problems in graph theory. It remains to be seen which problems can be solved rapidly using purely combinatorial algorithms, and which really require the continuous techniques developed in the past 20 years.

“This is a philosophical question that I’m trying to understand,” Nanongkai said. “This shortest-path problem gives some hope.”

rn // Define dataLayer and the gtag function.rn window.dataLayer = window.dataLayer || [];rn function gtag()dataLayer.push(arguments);rnrn // Default ad_storage to ‘denied’.rn gtag(‘consent’, ‘default’, rn ‘ad_storage’: ‘denied’rn );rnu003c/script>rnu003c!– Google Tag Manager –>rnu003cscript>(function(w,d,s,l,i)[];w[l].push(‘gtm.start’:rnnew Date().getTime(),event:’gtm.js’);var f=d.getElementsByTagName(s)[0],rnj=d.createElement(s),dl=l!=’dataLayer’?’&l=”+l:”‘;j.async=true;j.src=rn’ End Google Tag Manager –>rnu003c!– Google Tag Manager (noscript) –>rnu003cnoscript>u003ciframe src=” width=”0″ style=”display:none;visibility:hidden”>u003c/iframe>u003c/noscript>rnu003c!– End Google Tag Manager (noscript) –>rnu003cscript>rnfunction getCookie(name) rn let value = “; ” + document.cookie;rn var parts = value.split(“; ” + name + “=”);rn if (parts.length === 2) return parts.pop().split(“;”).shift();rnrnrnif(getCookie(‘acceptedPolicy’)) [];rn function gtag()dataLayer.push(arguments);rn gtag(‘js’, new Date());rnrn gtag(‘config’, ‘AW-10788252298′);rnrn else rn(function(i,s,o,g,r,a,m))(window,document,’script’,’ ‘UA-8526335-13’, storage: ‘none’ );rnga(‘set’, ‘anonymizeIp’, true);rnga(‘set’, ‘forceSSL’, true);rnga(‘require’, ‘displayfeatures’);rnga(‘send’,’pageview’);rnrnu003c/script>rn”,”google_analytics”:null,”tracking_scripts_no_cookie”:null,”google_analytics_no_cookie”:null,”popular_searches”:[“type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.popular_searches.0″,”typename”:”PopularSearch”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.popular_searches.1″,”typename”:”PopularSearch”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.popular_searches.2″,”typename”:”PopularSearch”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.popular_searches.3″,”typename”:”PopularSearch”],”search_topics”:[“type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.0″,”typename”:”SearchTopic”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.1″,”typename”:”SearchTopic”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.2″,”typename”:”SearchTopic”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.3″,”typename”:”SearchTopic”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.4″,”typename”:”SearchTopic”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.5″,”typename”:”SearchTopic”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.6″,”typename”:”SearchTopic”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.7″,”typename”:”SearchTopic”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.8″,”typename”:”SearchTopic”],”search_sections”:[“type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_sections.0″,”typename”:”Term”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_sections.1″,”typename”:”Term”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_sections.2″,”typename”:”Term”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_sections.3″,”typename”:”Term”],”search_authors”:[“type”:”id”,”generated”:false,”id”:”AuthorList:38171″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:28087″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:29794″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:39302″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:56″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:47249″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:29458″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:73″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:39164″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:59″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:8728″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:11648″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:42689″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:95″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:15493″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:450″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:36490″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:16315″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:2752″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:15492″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:68″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:62″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:13684″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:13691″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:50″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:15142″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:8084″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:742″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:11543″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:57″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:7262″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:70″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:19918″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:13695″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:32676″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:13724″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:26310″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:30207″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:19266″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:13251″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:17000″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:17149″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:5279″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:58″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:32612″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:27534″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:25173″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:64″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:47″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:14784″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:98″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:5830″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:6793″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:75″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:52″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:69″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:77″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:19092″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:20557″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:66″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:46418″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:85″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:37141″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:44758″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:49403″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:12170″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:32″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:51″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:44787″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:72″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:16475″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:91″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:10351″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:31716″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:1241″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:8463″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:49″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:16815″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:67″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:37462″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:87″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:36139″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:20556″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:90″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:39551″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:27374″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:40″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:47633″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:45758″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:38413″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:12570″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:38699″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:23451″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:79″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:38″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:47180″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:60″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:2333″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:3569″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:414″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:20495″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:47830″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:17147″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:30953″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:32437″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:38705″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:40613″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:7186″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:14093″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:34″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:23″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:74″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:19093″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:1472″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:6476″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:42264″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:10″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:37605″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:43298″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:37428″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:19962″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:24″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:1816″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:84″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:55″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:31″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:24011″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:100″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:2784″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:26114″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:9412″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:820″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:1666″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:20950″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:48″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:80″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:15681″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:24577″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:78″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:23845″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:83″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:35441″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:76″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:15680″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:7239″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:44197″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:65″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:5944″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:61″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:63″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:26311″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:71″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:17148″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:13356″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:17150″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:39768″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:2960″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:14785″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:3″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:54″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:88″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:12964″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:53″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:86″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:3244″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:89″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:15913″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:42263″,”typename”:”AuthorList”,”type”:”id”,”generated”:false,”id”:”AuthorList:45757″,”typename”:”AuthorList”],”address_to_editor”:[“type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.address_to_editor.0″,”typename”:”Editor”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.address_to_editor.1″,”typename”:”Editor”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.address_to_editor.2″,”typename”:”Editor”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.address_to_editor.3″,”typename”:”Editor”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.address_to_editor.4″,”typename”:”Editor”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.address_to_editor.5″,”typename”:”Editor”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.address_to_editor.6″,”typename”:”Editor”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.address_to_editor.7″,”typename”:”Editor”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.address_to_editor.8″,”typename”:”Editor”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.address_to_editor.9″,”typename”:”Editor”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.address_to_editor.10″,”typename”:”Editor”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.address_to_editor.11″,”typename”:”Editor”],”$ROOT_QUERY.options”:”acf”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf”,”typename”:”ThemeOptions”,”__typename”:”Options”,”$ROOT_QUERY.getPostPageArchive(“slug”:”finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118″,”type”:””).data.0.acf”:”custom_page_colors”:””,”page_accent_color”:null,”page_text_color”:null,”page_background_color”:null,”header_type”:”default”,”header_gradient_color”:null,”header_gradient_opacity”:null,”header_solid_colors”:””,”header_solid_primary_color”:null,”header_solid_secondary_color”:null,”header_solid_hover_color”:null,”header_transparent_colors”:null,”header_transparent_primary_color”:null,”header_transparent_secondary_color”:null,”header_transparent_hover_color”:null,”__typename”:”ACFFields”,”$ROOT_QUERY.getPostPageArchive(“slug”:”finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118″,”type”:””).data.0″:”acf”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.getPostPageArchive(“slug”:”finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118″,”type”:””).data.0.acf”,”typename”:”ACFFields”,”__typename”:”Post”,”$ROOT_QUERY.getPostPageArchive(“slug”:”finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118″,”type”:””)”:”data”:[“type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.getPostPageArchive(“slug”:”finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118″,”type”:””).data.0″,”typename”:”Post”],”__typename”:”PostPageArchive”,”$ROOT_QUERY.getPageMeta(“slug”:”finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118″,”type”:””)”: Quanta Magazine” />nu003cmeta name=”twitter:description” content=”Researchers can now find the shortest route through a network nearly as fast as theoretically possible, even when some steps can cancel out others.” />nu003cmeta name=”twitter:image” content=” />nu003cmeta name=”twitter:image:width” content=”1200″ />nu003cmeta name=”twitter:image:height” content=”630″ />nu003clink rel=”canonical” href=” />nu003cscript type=”application/ld+json”>”@context”:”https://schema.org”,”@type”:”BreadcrumbList”,”itemListElement”:[“@type”:”ListItem”,”position”:1,”item”: Science and Math News”,”@type”:”ListItem”,”position”:2,”item”:”@id”:” Science News, Interviews and Columns From Quanta Magazine”,”@type”:”ListItem”,”position”:3,”item”:”@id”:”,”name”:”Finally, a Fast Algorithm for Shortest Paths on Negative Graphs”]u003c/script>n”,”__typename”:”PageMeta”,”$ROOT_QUERY.options.acf.social_media_links.0″:”type”:”facebook”,”label”:”Facebook”,”url”:” Joy of Why”,”slug”:”the-joy-of-why”,”description”:”The mathematician and author Steven Strogatz interviews leading researchers about the great scientific and mathematical questions of our time.”,”featured_image”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.channels.0.featured_image”,”typename”:”Image”,”square_image”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.channels.0.square_image”,”typename”:”Image”,”subscribe_itunes_link”:” Science Podcast”,”slug”:”quanta-podcast”,”description”:”Susan Valot narrates in-depth news episodes based on u003ci>Quanta Magazineu003c/i>’s articles about mathematics, physics, biology and computer science. “,”featured_image”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.channels.1.featured_image”,”typename”:”Image”,”square_image”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.channels.1.square_image”,”typename”:”Image”,”subscribe_itunes_link”:” frog leaps out of the frame of the video.”,”caption”:””,”url”:” Joy of x”,”slug”:”the-joy-of-x”,”description”:”The acclaimed mathematician and author Steven Strogatz interviews some of the world’s leading scientists about their lives and work.”,”featured_image”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.channels.2.featured_image”,”typename”:”Image”,”square_image”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.channels.2.square_image”,”typename”:”Image”,”subscribe_itunes_link”:” holes”,”label”:”Black Holes”,”__typename”:”PopularSearch”,”$ROOT_QUERY.options.acf.popular_searches.3″:”term”:”evolution”,”label”:”Evolution”,”__typename”:”PopularSearch”,”$ROOT_QUERY.options.acf.search_topics.0″:”type”:”Tag”,”label”:”Podcasts”,”tag”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.0.tag”,”typename”:”Term”,”category”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.0.category”,”typename”:”Term”,”__typename”:”SearchTopic”,”$ROOT_QUERY.options.acf.search_topics.0.tag”:”name”:”Quanta Podcast”,”slug”:”quanta-podcast”,”term_id”:”552″,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.0.category”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.1″:”type”:”Tag”,”label”:”Columns”,”tag”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.1.tag”,”typename”:”Term”,”category”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.1.category”,”typename”:”Term”,”__typename”:”SearchTopic”,”$ROOT_QUERY.options.acf.search_topics.1.tag”:”name”:”Quantized Columns”,”slug”:”quantized”,”term_id”:”551″,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.1.category”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.2″:”type”:”Series”,”label”:”Series”,”tag”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.2.tag”,”typename”:”Term”,”category”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.2.category”,”typename”:”Term”,”__typename”:”SearchTopic”,”$ROOT_QUERY.options.acf.search_topics.2.tag”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.2.category”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.3″:”type”:”Category”,”label”:”Interviews”,”tag”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.3.tag”,”typename”:”Term”,”category”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.3.category”,”typename”:”Term”,”__typename”:”SearchTopic”,”$ROOT_QUERY.options.acf.search_topics.3.tag”:”name”:”Q&A”,”slug”:”qa”,”term_id”:”567″,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.3.category”:”name”:”Q&A”,”slug”:”qa”,”term_id”:”176″,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.4″:”type”:”Category”,”label”:”Multimedia”,”tag”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.4.tag”,”typename”:”Term”,”category”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.4.category”,”typename”:”Term”,”__typename”:”SearchTopic”,”$ROOT_QUERY.options.acf.search_topics.4.tag”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.4.category”:”name”:”Multimedia”,”slug”:”multimedia”,”term_id”:”43″,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.5″:”type”:”Category”,”label”:”Puzzles”,”tag”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.5.tag”,”typename”:”Term”,”category”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.5.category”,”typename”:”Term”,”__typename”:”SearchTopic”,”$ROOT_QUERY.options.acf.search_topics.5.tag”:”name”:”puzzles”,”slug”:”puzzles”,”term_id”:”542″,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.5.category”:”name”:”Puzzles”,”slug”:”puzzles”,”term_id”:”546″,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.6″:”type”:”Category”,”label”:”Blog Posts”,”tag”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.6.tag”,”typename”:”Term”,”category”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.6.category”,”typename”:”Term”,”__typename”:”SearchTopic”,”$ROOT_QUERY.options.acf.search_topics.6.tag”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.6.category”:”name”:”Abstractions blog”,”slug”:”abstractions”,”term_id”:”619″,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.7″:”type”:”news”,”label”:”News Articles”,”tag”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.7.tag”,”typename”:”Term”,”category”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.7.category”,”typename”:”Term”,”__typename”:”SearchTopic”,”$ROOT_QUERY.options.acf.search_topics.7.tag”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.7.category”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.8″:”type”:”videos”,”label”:”Videos”,”tag”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.8.tag”,”typename”:”Term”,”category”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.options.acf.search_topics.8.category”,”typename”:”Term”,”__typename”:”SearchTopic”,”$ROOT_QUERY.options.acf.search_topics.8.tag”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_topics.8.category”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_sections.0″:”name”:”Mathematics”,”slug”:”mathematics”,”term_id”:”188″,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_sections.1″:”name”:”Physics”,”slug”:”physics”,”term_id”:”189″,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_sections.2″:”name”:”Biology”,”slug”:”biology”,”term_id”:”191″,”__typename”:”Term”,”$ROOT_QUERY.options.acf.search_sections.3″:”name”:”Computer Science”,”slug”:”computer-science”,”term_id”:”190″,”__typename”:”Term”,”AuthorList:38171″:”id”:”38171″,”name”:”Adam Becker”,”__typename”:”AuthorList”,”AuthorList:28087″:”id”:”28087″,”name”:”Adam Mann”,”__typename”:”AuthorList”,”AuthorList:29794″:”id”:”29794″,”name”:”Alex Kontorovich”,”__typename”:”AuthorList”,”AuthorList:39302″:”id”:”39302″,”name”:”Alexander Hellemans”,”__typename”:”AuthorList”,”AuthorList:56″:”id”:”56″,”name”:”Alla Katsnelson”,”__typename”:”AuthorList”,”AuthorList:47249″:”id”:”47249″,”name”:”Allison Parshall”,”__typename”:”AuthorList”,”AuthorList:29458″:”id”:”29458″,”name”:”Allison Whitten”,”__typename”:”AuthorList”,”AuthorList:73″:”id”:”73″,”name”:”Amanda Gefter”,”__typename”:”AuthorList”,”AuthorList:39164″:”id”:”39164″,”name”:”Ana Kova”,”__typename”:”AuthorList”,”AuthorList:59″:”id”:”59″,”name”:”Andreas von Bubnoff”,”__typename”:”AuthorList”,”AuthorList:8728″:”id”:”8728″,”name”:”Anil Ananthaswamy”,”__typename”:”AuthorList”,”AuthorList:11648″:”id”:”11648″,”name”:”Ann Finkbeiner”,”__typename”:”AuthorList”,”AuthorList:42689″:”id”:”42689″,”name”:”Annie Melchor”,”__typename”:”AuthorList”,”AuthorList:95″:”id”:”95″,”name”:”Ariel Bleicher”,”__typename”:”AuthorList”,”AuthorList:15493″:”id”:”15493″,”name”:”Ashley Smart”,”__typename”:”AuthorList”,”AuthorList:450″:”id”:”450″,”name”:”Ashley Yeager”,”__typename”:”AuthorList”,”AuthorList:36490″:”id”:”36490″,”name”:”Ben Brubaker”,”__typename”:”AuthorList”,”AuthorList:16315″:”id”:”16315″,”name”:”Bill Andrews”,”__typename”:”AuthorList”,”AuthorList:2752″:”id”:”2752″,”name”:”Bob Henderson”,”__typename”:”AuthorList”,”AuthorList:15492″:”id”:”15492″,”name”:”Brendan Z. Foster”,”__typename”:”AuthorList”,”AuthorList:68″:”id”:”68″,”name”:”Brooke Borel”,”__typename”:”AuthorList”,”AuthorList:62″:”id”:”62″,”name”:”Carl Zimmer”,”__typename”:”AuthorList”,”AuthorList:13684″:”id”:”13684″,”name”:”Caroline Lee”,”__typename”:”AuthorList”,”AuthorList:13691″:”id”:”13691″,”name”:”Caroline Lee”,”__typename”:”AuthorList”,”AuthorList:50″:”id”:”50″,”name”:”Carrie Arnold”,”__typename”:”AuthorList”,”AuthorList:15142″:”id”:”15142″,”name”:”Chanda Prescod-Weinstein”,”__typename”:”AuthorList”,”AuthorList:8084″:”id”:”8084″,”name”:”Charlie Wood”,”__typename”:”AuthorList”,”AuthorList:742″:”id”:”742″,”name”:”Christie Wilcox”,”__typename”:”AuthorList”,”AuthorList:11543″:”id”:”11543″,”name”:”Claudia Dreifus”,”__typename”:”AuthorList”,”AuthorList:57″:”id”:”57″,”name”:”Courtney Humphries”,”__typename”:”AuthorList”,”AuthorList:7262″:”id”:”7262″,”name”:”Dalmeet Singh Chawla”,”__typename”:”AuthorList”,”AuthorList:70″:”id”:”70″,”name”:”Dan Falk”,”__typename”:”AuthorList”,”AuthorList:19918″:”id”:”19918″,”name”:”Dana Najjar”,”__typename”:”AuthorList”,”AuthorList:13695″:”id”:”13695″,”name”:”Daniel Garisto”,”__typename”:”AuthorList”,”AuthorList:32676″:”id”:”32676″,”name”:”Daniel S. Freed”,”__typename”:”AuthorList”,”AuthorList:13724″:”id”:”13724″,”name”:”David H. Freedman”,”__typename”:”AuthorList”,”AuthorList:26310″:”id”:”26310″,”name”:”David S. Richeson”,”__typename”:”AuthorList”,”AuthorList:30207″:”id”:”30207″,”name”:”David Tse”,”__typename”:”AuthorList”,”AuthorList:19266″:”id”:”19266″,”name”:”Devin Powell”,”__typename”:”AuthorList”,”AuthorList:13251″:”id”:”13251″,”name”:”Diana Kwon”,”__typename”:”AuthorList”,”AuthorList:17000″:”id”:”17000″,”name”:”Elena Renken”,”__typename”:”AuthorList”,”AuthorList:17149″:”id”:”17149″,”name”:”Elizabeth Landau”,”__typename”:”AuthorList”,”AuthorList:5279″:”id”:”5279″,”name”:”Elizabeth Preston”,”__typename”:”AuthorList”,”AuthorList:58″:”id”:”58″,”name”:”Elizabeth Svoboda”,”__typename”:”AuthorList”,”AuthorList:32612″:”id”:”32612″,”name”:”Ellen Horne”,”__typename”:”AuthorList”,”AuthorList:27534″:”id”:”27534″,”name”:”Emily Buder”,”__typename”:”AuthorList”,”AuthorList:25173″:”id”:”25173″,”name”:”Emily Levesque”,”__typename”:”AuthorList”,”AuthorList:64″:”id”:”64″,”name”:”Emily Singer”,”__typename”:”AuthorList”,”AuthorList:47″:”id”:”47″,”name”:”Erica Klarreich”,”__typename”:”AuthorList”,”AuthorList:14784″:”id”:”14784″,”name”:”Erika K. Carlson”,”__typename”:”AuthorList”,”AuthorList:98″:”id”:”98″,”name”:”Esther Landhuis”,”__typename”:”AuthorList”,”AuthorList:5830″:”id”:”5830″,”name”:”Eva Silverstein”,”__typename”:”AuthorList”,”AuthorList:6793″:”id”:”6793″,”name”:”Evelyn Lamb”,”__typename”:”AuthorList”,”AuthorList:75″:”id”:”75″,”name”:”Ferris Jabr”,”__typename”:”AuthorList”,”AuthorList:52″:”id”:”52″,”name”:”Frank Wilczek”,”__typename”:”AuthorList”,”AuthorList:69″:”id”:”69″,”name”:”Gabriel Popkin”,”__typename”:”AuthorList”,”AuthorList:77″:”id”:”77″,”name”:”George Musser”,”__typename”:”AuthorList”,”AuthorList:19092″:”id”:”19092″,”name”:”Grant Sanderson”,”__typename”:”AuthorList”,”AuthorList:20557″:”id”:”20557″,”name”:”Howard Lee”,”__typename”:”AuthorList”,”AuthorList:66″:”id”:”66″,”name”:”Ingrid Daubechies”,”__typename”:”AuthorList”,”AuthorList:46418″:”id”:”46418″,”name”:”Ingrid Wickelgren”,”__typename”:”AuthorList”,”AuthorList:85″:”id”:”85″,”name”:”Ivan Amato”,”__typename”:”AuthorList”,”AuthorList:37141″:”id”:”37141″,”name”:”Jake Buehler”,”__typename”:”AuthorList”,”AuthorList:44758″:”id”:”44758″,”name”:”James Dinneen”,”__typename”:”AuthorList”,”AuthorList:49403″:”id”:”49403″,”name”:”James R. Riordon”,”__typename”:”AuthorList”,”AuthorList:12170″:”id”:”12170″,”name”:”Janna Levin”,”__typename”:”AuthorList”,”AuthorList:32″:”id”:”32″,”name”:”Jeanette Kazmierczak”,”__typename”:”AuthorList”,”AuthorList:51″:”id”:”51″,”name”:”Jennifer Ouellette”,”__typename”:”AuthorList”,”AuthorList:44787″:”id”:”44787″,”name”:”Joanna Thompson”,”__typename”:”AuthorList”,”AuthorList:72″:”id”:”72″,”name”:”John Pavlus”,”__typename”:”AuthorList”,”AuthorList:16475″:”id”:”16475″,”name”:”John Preskill”,”__typename”:”AuthorList”,”AuthorList:91″:”id”:”91″,”name”:”John Rennie”,”__typename”:”AuthorList”,”AuthorList:10351″:”id”:”10351″,”name”:”Jonathan Lambert”,”__typename”:”AuthorList”,”AuthorList:31716″:”id”:”31716″,”name”:”Jonathan O’Callaghan”,”__typename”:”AuthorList”,”AuthorList:1241″:”id”:”1241″,”name”:”Jordana Cepelewicz”,”__typename”:”AuthorList”,”AuthorList:8463″:”id”:”8463″,”name”:”Joshua Roebke”,”__typename”:”AuthorList”,”AuthorList:49″:”id”:”49″,”name”:”Joshua Sokol”,”__typename”:”AuthorList”,”AuthorList:16815″:”id”:”16815″,”name”:”jye”,”__typename”:”AuthorList”,”AuthorList:67″:”id”:”67″,”name”:”K.C. Cole”,”__typename”:”AuthorList”,”AuthorList:37462″:”id”:”37462″,”name”:”Karmela Padavic-Callaghan”,”__typename”:”AuthorList”,”AuthorList:87″:”id”:”87″,”name”:”Kat McGowan”,”__typename”:”AuthorList”,”AuthorList:36139″:”id”:”36139″,”name”:”Katarina Zimmer”,”__typename”:”AuthorList”,”AuthorList:20556″:”id”:”20556″,”name”:”Katherine Harmon Courage”,”__typename”:”AuthorList”,”AuthorList:90″:”id”:”90″,”name”:”Katia Moskvitch”,”__typename”:”AuthorList”,”AuthorList:39551″:”id”:”39551″,”name”:”Katie McCormick”,”__typename”:”AuthorList”,”AuthorList:27374″:”id”:”27374″,”name”:”Kelsey Houston-Edwards”,”__typename”:”AuthorList”,”AuthorList:40″:”id”:”40″,”name”:”Kevin Hartnett”,”__typename”:”AuthorList”,”AuthorList:47633″:”id”:”47633″,”name”:”Konstantin Kakaes”,”__typename”:”AuthorList”,”AuthorList:45758″:”id”:”45758″,”name”:”Kristina Armitage”,”__typename”:”AuthorList”,”AuthorList:38413″:”id”:”38413″,”name”:”Lakshmi Chandrasekaran”,”__typename”:”AuthorList”,”AuthorList:12570″:”id”:”12570″,”name”:”Laura Poppick”,”__typename”:”AuthorList”,”AuthorList:38699″:”id”:”38699″,”name”:”Leila Sloman”,”__typename”:”AuthorList”,”AuthorList:23451″:”id”:”23451″,”name”:”Liam Drew”,”__typename”:”AuthorList”,”AuthorList:79″:”id”:”79″,”name”:”Liz Kruesi”,”__typename”:”AuthorList”,”AuthorList:38″:”id”:”38″,”name”:”Lucy Reading-Ikkanda”,”__typename”:”AuthorList”,”AuthorList:47180″:”id”:”47180″,”name”:”Lyndie Chiou”,”__typename”:”AuthorList”,”AuthorList:60″:”id”:”60″,”name”:”Maggie McKee”,”__typename”:”AuthorList”,”AuthorList:2333″:”id”:”2333″,”name”:”Mallory Locklear”,”__typename”:”AuthorList”,”AuthorList:3569″:”id”:”3569″,”name”:”Marcus Woo”,”__typename”:”AuthorList”,”AuthorList:414″:”id”:”414″,”name”:”Mark Kim-Mulgrew”,”__typename”:”AuthorList”,”AuthorList:20495″:”id”:”20495″,”name”:”Matt Carlstrom”,”__typename”:”AuthorList”,”AuthorList:47830″:”id”:”47830″,”name”:”Matt von Hippel”,”__typename”:”AuthorList”,”AuthorList:17147″:”id”:”17147″,”name”:”Matthew Hutson”,”__typename”:”AuthorList”,”AuthorList:30953″:”id”:”30953″,”name”:”Max G. Levy”,”__typename”:”AuthorList”,”AuthorList:32437″:”id”:”32437″,”name”:”Max Kozlov”,”__typename”:”AuthorList”,”AuthorList:38705″:”id”:”38705″,”name”:”mcho”,”__typename”:”AuthorList”,”AuthorList:40613″:”id”:”40613″,”name”:”Melanie Mitchell”,”__typename”:”AuthorList”,”AuthorList:7186″:”id”:”7186″,”name”:”Melinda Wenner Moyer”,”__typename”:”AuthorList”,”AuthorList:14093″:”id”:”14093″,”name”:”Michael Harris”,”__typename”:”AuthorList”,”AuthorList:34″:”id”:”34″,”name”:”Michael Kranz”,”__typename”:”AuthorList”,”AuthorList:23″:”id”:”23″,”name”:”Michael Moyer”,”__typename”:”AuthorList”,”AuthorList:74″:”id”:”74″,”name”:”Michael Nielsen”,”__typename”:”AuthorList”,”AuthorList:19093″:”id”:”19093″,”name”:”Michele Bannister”,”__typename”:”AuthorList”,”AuthorList:1472″:”id”:”1472″,”name”:”Moira Chas”,”__typename”:”AuthorList”,”AuthorList:6476″:”id”:”6476″,”name”:”Monique Brouillette”,”__typename”:”AuthorList”,”AuthorList:42264″:”id”:”42264″,”name”:”Mordechai Rorvig”,”__typename”:”AuthorList”,”AuthorList:10″:”id”:”10″,”name”:”Natalie Wolchover”,”__typename”:”AuthorList”,”AuthorList:37605″:”id”:”37605″,”name”:”Nick Thieme”,”__typename”:”AuthorList”,”AuthorList:43298″:”id”:”43298″,”name”:”Nicole Yunger Halpern”,”__typename”:”AuthorList”,”AuthorList:37428″:”id”:”37428″,”name”:”Nima Arkani-Hamed”,”__typename”:”AuthorList”,”AuthorList:19962″:”id”:”19962″,”name”:”Nola Taylor Redd”,”__typename”:”AuthorList”,”AuthorList:24″:”id”:”24″,”name”:”Olena Shmahalo”,”__typename”:”AuthorList”,”AuthorList:1816″:”id”:”1816″,”name”:”Patrick Honner”,”__typename”:”AuthorList”,”AuthorList:84″:”id”:”84″,”name”:”Peter Byrne”,”__typename”:”AuthorList”,”AuthorList:55″:”id”:”55″,”name”:”Philip Ball”,”__typename”:”AuthorList”,”AuthorList:31″:”id”:”31″,”name”:”Pradeep Mutalik”,”__typename”:”AuthorList”,”AuthorList:24011″:”id”:”24011″,”name”:”Puja Changoiwala”,”__typename”:”AuthorList”,”AuthorList:100″:”id”:”100″,”name”:”Quanta Magazine”,”__typename”:”AuthorList”,”AuthorList:2784″:”id”:”2784″,”name”:”R. Douglas Fields”,”__typename”:”AuthorList”,”AuthorList:26114″:”id”:”26114″,”name”:”Rachel Crowell”,”__typename”:”AuthorList”,”AuthorList:9412″:”id”:”9412″,”name”:”Raleigh McElvery”,”__typename”:”AuthorList”,”AuthorList:820″:”id”:”820″,”name”:”Ramin Skibba”,”__typename”:”AuthorList”,”AuthorList:1666″:”id”:”1666″,”name”:”Rebecca Boyle”,”__typename”:”AuthorList”,”AuthorList:20950″:”id”:”20950″,”name”:”Richard Masland”,”__typename”:”AuthorList”,”AuthorList:48″:”id”:”48″,”name”:”Robbert Dijkgraaf”,”__typename”:”AuthorList”,”AuthorList:80″:”id”:”80″,”name”:”Roberta Kwok”,”__typename”:”AuthorList”,”AuthorList:15681″:”id”:”15681″,”name”:”Robin George Andrews”,”__typename”:”AuthorList”,”AuthorList:24577″:”id”:”24577″,”name”:”Rodrigo Pérez Ortega”,”__typename”:”AuthorList”,”AuthorList:78″:”id”:”78″,”name”:”Sabine Hossenfelder”,”__typename”:”AuthorList”,”AuthorList:23845″:”id”:”23845″,”name”:”Samuel Velasco”,”__typename”:”AuthorList”,”AuthorList:83″:”id”:”83″,”name”:”Sarah Lewin”,”__typename”:”AuthorList”,”AuthorList:35441″:”id”:”35441″,”name”:”Scott Aaronson”,”__typename”:”AuthorList”,”AuthorList:76″:”id”:”76″,”name”:”Sean B. Carroll”,”__typename”:”AuthorList”,”AuthorList:15680″:”id”:”15680″,”name”:”Sean Carroll”,”__typename”:”AuthorList”,”AuthorList:7239″:”id”:”7239″,”name”:”Shannon Hall”,”__typename”:”AuthorList”,”AuthorList:44197″:”id”:”44197″,”name”:”Sheon Han”,”__typename”:”AuthorList”,”AuthorList:65″:”id”:”65″,”name”:”Siobhan Roberts”,”__typename”:”AuthorList”,”AuthorList:5944″:”id”:”5944″,”name”:”Sophia Chen”,”__typename”:”AuthorList”,”AuthorList:61″:”id”:”61″,”name”:”Steph Yin”,”__typename”:”AuthorList”,”AuthorList:63″:”id”:”63″,”name”:”Stephanie Bucklin”,”__typename”:”AuthorList”,”AuthorList:26311″:”id”:”26311″,”name”:”Stephanie DeMarco”,”__typename”:”AuthorList”,”AuthorList:71″:”id”:”71″,”name”:”Stephen Ornes”,”__typename”:”AuthorList”,”AuthorList:17148″:”id”:”17148″,”name”:”Steve Nadis”,”__typename”:”AuthorList”,”AuthorList:13356″:”id”:”13356″,”name”:”Steven Strogatz”,”__typename”:”AuthorList”,”AuthorList:17150″:”id”:”17150″,”name”:”Susan D’Agostino”,”__typename”:”AuthorList”,”AuthorList:39768″:”id”:”39768″,”name”:”Tamar Lichter Blanks”,”__typename”:”AuthorList”,”AuthorList:2960″:”id”:”2960″,”name”:”Tara C. Smith”,”__typename”:”AuthorList”,”AuthorList:14785″:”id”:”14785″,”name”:”Thomas Lewton”,”__typename”:”AuthorList”,”AuthorList:3″:”id”:”3″,”name”:”Thomas Lin”,”__typename”:”AuthorList”,”AuthorList:54″:”id”:”54″,”name”:”Tim Vernimmen”,”__typename”:”AuthorList”,”AuthorList:88″:”id”:”88″,”name”:”Tom Siegfried”,”__typename”:”AuthorList”,”AuthorList:12964″:”id”:”12964″,”name”:”Vanessa Schipani”,”__typename”:”AuthorList”,”AuthorList:53″:”id”:”53″,”name”:”Veronique Greenwood”,”__typename”:”AuthorList”,”AuthorList:86″:”id”:”86″,”name”:”Virginia Hughes”,”__typename”:”AuthorList”,”AuthorList:3244″:”id”:”3244″,”name”:”Viviane Callier”,”__typename”:”AuthorList”,”AuthorList:89″:”id”:”89″,”name”:”Wynne Parry”,”__typename”:”AuthorList”,”AuthorList:15913″:”id”:”15913″,”name”:”XiaoZhi Lim”,”__typename”:”AuthorList”,”AuthorList:42263″:”id”:”42263″,”name”:”Yasemin Saplakoglu”,”__typename”:”AuthorList”,”AuthorList:45757″:”id”:”45757″,”name”:”Zack Savitsky”,”__typename”:”AuthorList”,”$ROOT_QUERY.options.acf.address_to_editor.0″:”name”:”Bill Andrews – Senior CS Editor”,”__typename”:”Editor”,”$ROOT_QUERY.options.acf.address_to_editor.1″:”name”:”Ben Brubaker – Staff CS Writer”,”__typename”:”Editor”,”$ROOT_QUERY.options.acf.address_to_editor.2″:”name”:”Matt Carlstrom – Senior Engagement Editor”,”__typename”:”Editor”,”$ROOT_QUERY.options.acf.address_to_editor.3″:”name”:”Jordana Cepelewicz – Senior Math Writer”,”__typename”:”Editor”,”$ROOT_QUERY.options.acf.address_to_editor.4″:”name”:”Konstantin Kakaes – Senior Math Editor”,”__typename”:”Editor”,”$ROOT_QUERY.options.acf.address_to_editor.5″:”name”:”Thomas Lin – Editor in Chief”,”__typename”:”Editor”,”$ROOT_QUERY.options.acf.address_to_editor.6″:”name”:”Michael Moyer – Deputy Editor, Physics, Math, CS”,”__typename”:”Editor”,”$ROOT_QUERY.options.acf.address_to_editor.7″:”name”:”John Rennie – Deputy Editor, Biology, Podcasts”,”__typename”:”Editor”,”$ROOT_QUERY.options.acf.address_to_editor.8″:”name”:”Yasemin Saplakoglu – Staff Biology Writer”,”__typename”:”Editor”,”$ROOT_QUERY.options.acf.address_to_editor.9″:”name”:”Samuel Velasco – Art Director”,”__typename”:”Editor”,”$ROOT_QUERY.options.acf.address_to_editor.10″:”name”:”Natalie Wolchover – Senior Physics Editor”,”__typename”:”Editor”,”$ROOT_QUERY.options.acf.address_to_editor.11″:”name”:”Charlie Wood – Staff Physics Writer”,”__typename”:”Editor”,”$ROOT_QUERY.menu(“slug”:”main-menu”).items.0″:”title”:”Physics”,”url”:” Science”,”url”:”https://www.quantamagazine.org/computer-science/”,”order”:4,”__typename”:”MenuItem”,”$ROOT_QUERY.menu(“slug”:”main-menu”).items.4″:”title”:”Topics”,”url”:”https://news.google.com/topics”,”order”:5,”__typename”:”MenuItem”,”$ROOT_QUERY.menu(“slug”:”main-menu”).items.5″:”title”:”Archive”,”url”:”https://www.quantamagazine.org/archive/”,”order”:6,”__typename”:”MenuItem”,”$ROOT_QUERY.menu(“slug”:”main-menu”)”:”items”:[“type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”main-menu”).items.0″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”main-menu”).items.1″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”main-menu”).items.2″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”main-menu”).items.3″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”main-menu”).items.4″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”main-menu”).items.5″,”typename”:”MenuItem”],”__typename”:”Menu”,”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.0″:”title”:”Blog”,”url”:”https://www.quantamagazine.org/abstractions/”,”order”:1,”__typename”:”MenuItem”,”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.1″:”title”:”Q&A”,”url”:”https://www.quantamagazine.org/qa/”,”order”:2,”__typename”:”MenuItem”,”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.2″:”title”:”Columns”,”url”:”/tag/quantized”,”order”:3,”__typename”:”MenuItem”,”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.3″:”title”:”Puzzles”,”url”:”https://www.quantamagazine.org/puzzles/”,”order”:4,”__typename”:”MenuItem”,”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.4″:”title”:”Podcasts”,”url”:”/podcasts/”,”order”:5,”__typename”:”MenuItem”,”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.5″:”title”:”Videos”,”url”:”/videos”,”order”:6,”__typename”:”MenuItem”,”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.6″:”title”:”Multimedia”,”url”:”https://www.quantamagazine.org/multimedia/”,”order”:7,”__typename”:”MenuItem”,”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.7″:”title”:”About Quanta”,”url”:”https://www.quantamagazine.org/about/”,”order”:8,”__typename”:”MenuItem”,”$ROOT_QUERY.menu(“slug”:”secondary-menu”)”:”items”:[“type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.0″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.1″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.2″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.3″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.4″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.5″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.6″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”secondary-menu”).items.7″,”typename”:”MenuItem”],”__typename”:”Menu”,”$ROOT_QUERY.menu(“slug”:”footer”).items.0″:”title”:”About Quanta”,”url”:” Us”,”url”:” & Conditions”,”url”:” Policy”,”url”:” Foundation”,”url”:”http://www.simonsfoundation.org”,”order”:6,”__typename”:”MenuItem”,”$ROOT_QUERY.menu(“slug”:”footer”)”:”items”:[“type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”footer”).items.0″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”footer”).items.1″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”footer”).items.2″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”footer”).items.3″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”footer”).items.4″,”typename”:”MenuItem”,”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.menu(“slug”:”footer”).items.5″,”typename”:”MenuItem”],”__typename”:”Menu”,”$ROOT_QUERY.getPostPageArchive(“slug”:”finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118″)”:”type”:”post”,”meta”:”type”:”id”,”generated”:true,”id”:”$ROOT_QUERY.getPostPageArchive(“slug”:”finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118″).meta”,”typename”:”PageData”,”data”:[“type”:”id”,”generated”:false,”id”:”Post:122171″,”typename”:”Post”],”__typename”:”PostPageArchive”,”$ROOT_QUERY.getPostPageArchive(“slug”:”finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118″).meta”:”title”:”Finally, a Fast Algorithm for Shortest Paths on Negative Graphs ,”Author:null”:”id”:null,”name”:null,”link”:null,”description”:null,”url”:null,”public_email”:null,”facebook”:null,”twitter”:null,”instagram”:null,”acf”:null,”__typename”:”Author”,”Term:null”:”id”:null,”slug”:null,”name”:null,”link”:null,”description”:null,”image”:””,”__typename”:”Term”,”Post:122171″:”id”:”122171″,”title”:”Finally, a Fast Algorithm for Shortest Paths on Negative Graphs”,”excerpt”:”u003cp>Researchers can now find the shortest route through a network nearly as fast as theoretically possible, even when some steps can cancel out others.u003c/p>n”,”link”:” https://www.quantamagazine.org/?p=122171″,”date”:”2023-01-18T12:02:40″,”featured_media_image”:null,”authors”:[“type”:”id”,”generated”:true,”id”:”Post:122171.authors.0″,”typename”:”Author”],”tags”:[“type”:”id”,”generated”:true,”id”:”Post:122171.tags.0″,”typename”:”Term”,”type”:”id”,”generated”:true,”id”:”Post:122171.tags.1″,”typename”:”Term”,”type”:”id”,”generated”:true,”id”:”Post:122171.tags.2″,”typename”:”Term”,”type”:”id”,”generated”:true,”id”:”Post:122171.tags.3″,”typename”:”Term”,”type”:”id”,”generated”:true,”id”:”Post:122171.tags.4″,”typename”:”Term”,”type”:”id”,”generated”:true,”id”:”Post:122171.tags.5″,”typename”:”Term”],”podcast”:null,”acf”:”type”:”id”,”generated”:true,”id”:”$Post:122171.acf”,”typename”:”ACFFields”,”__typename”:”Post”,”status”:”publish”,”content”:””,”categories”:[“type”:”id”,”generated”:false,”id”:”Term:190″,”typename”:”Term”,”type”:”id”,”generated”:false,”id”:”Term:188″,”typename”:”Term”],”attachments”:null,”series_prev”:null,”series_next”:null,”next”:”type”:”id”,”generated”:true,”id”:”$Post:122171.next”,”typename”:”PostPageArchive”,”Post:122171.authors.0″:”name”:”Ben Brubaker”,”link”:” science”,”link”:” theory”,”link”:” science”,”link”:”https://www.quantamagazine.org/tag/network-science/”,”Post:122171.tags.5″:”slug”:”networks”,”__typename”:”Term”,”name”:”networks”,”link”:”https://www.quantamagazine.org/tag/networks/”,”$Post:122171.acf”:”featured_block_title”:””,”kicker”:”type”:”id”,”generated”:true,”id”:”$Post:122171.acf.kicker”,”typename”:”Term”,”featured_image_default”:”type”:”id”,”generated”:true,”id”:”$Post:122171.acf.featured_image_default”,”typename”:”Image”,”featured_image_square”:”type”:”id”,”generated”:true,”id”:”$Post:122171.acf.featured_image_square”,”typename”:”Image”,”featured_image_full_width”:”type”:”id”,”generated”:true,”id”:”$Post:122171.acf.featured_image_full_width”,”typename”:”Image”,”featured_image_gif”:false,”featured_video”:”false”,”full_page_interactive”:false,”podcast_publish_date”:””,”__typename”:”ACFFields”,”interactive_type”:null,”iframe_url”:null,”return_cursor”:null,”exclude_blurb”:null,”interactive_html”:null,”interactive_css”:null,”interactive_js”:null,”interactive_blurb”:null,”related_article”:null,”modules”:[“type”:”id”,”generated”:true,”id”:”$Post:122171.acf.modules.0″,”typename”:”ACFImageComponent”,”type”:”id”,”generated”:true,”id”:”$Post:122171.acf.modules.1″,”typename”:”ACFContent”],”template”:”article”,”subtitle”:”Researchers can now find the shortest route through a network nearly as fast as theoretically possible, even when some steps can cancel out others.rn”,”title_layout”:”default”,”title_background_type”:null,”title_background_image”:null,”title_background_video”:null,”title_background_attribution”:null,”title_background_image_gif”:null,”title_overlay_enable”:null,”title_overlay_color”:null,”title_overlay_opacity”:null,”title_text_color”:null,”featured_image_attribution”:”u003cp>Samuel Velasco/Quanta Magazineu003c/p>n”,”featured_overlay_enable”:”false”,”featured_overlay_color”:null,”featured_overlay_opacity”:null,”series”:”type”:”id”,”generated”:true,”id”:”$Post:122171.acf.series”,”typename”:”Term”,”intro_content”:null,”make_image_full_width”:null,”hide_ad_on_post”:false,”$Post:122171.acf.kicker”:”name”:”graph theory”,”link”:” Science”,”slug”:”computer-science”,”link”:” Writer”,”avatar”:”type”:”id”,”generated”:true,”id”:”$Post:122171.authors.0.acf.avatar”,”typename”:”Image”,”__typename”:”AuthorACF”,”$Post:122171.authors.0.acf.avatar”:”alt”:””,”caption”:””,”url”:” Velasco/Quanta Magazineu003c/p>n”,”caption”:””,”mobile_comp_caption”:””,”mobile_comp_attribution”:””,”sets”:[“type”:”id”,”generated”:true,”id”:”$Post:122171.acf.modules.0.sets.0″,”typename”:”ImageSet”],”__typename”:”ACFImageComponent”,”$Post:122171.acf.modules.0.sets.0″:”settings”:””,”image”:”type”:”id”,”generated”:true,”id”:”$Post:122171.acf.modules.0.sets.0.image”,”typename”:”Image”,”mobile_image”:”type”:”id”,”generated”:true,”id”:”$Post:122171.acf.modules.0.sets.0.mobile_image”,”typename”:”Image”,”mobile_side_margins”:false,”mobile_width_constraint”:””,”mobile_caption”:””,”mobile_attribution”:””,”zoom_image”:”type”:”id”,”generated”:true,”id”:”$Post:122171.acf.modules.0.sets.0.zoom_image”,”typename”:”Image”,”zoom_caption”:””,”zoom_attribution”:””,”mobile_zoom_image”:”type”:”id”,”generated”:true,”id”:”$Post:122171.acf.modules.0.sets.0.mobile_zoom_image”,”typename”:”Image”,”mobile_zoom_caption”:””,”mobile_zoom_attribution”:””,”external_link”:””,”__typename”:”ImageSet”,”$Post:122171.acf.modules.0.sets.0.image”:{“alt”:””,”caption”:””,”url”:” algorithms, as in life, negativity can be a drag.u003c/p>nu003cp>Consider the problem of finding the shortest path between two points on a graph — a network of nodes connected by links, or edges. Often, these edges aren’t interchangeable: A graph could represent a road map on which some roads are slower than others or have higher tolls. Computer scientists account for these differences by pairing each edge with a “weight” that quantifies the cost of moving across that segment — whether that cost represents time, money or something else. Since the 1950s, they’ve known how to find shortest paths essentially as fast as theoretically possible, assuming all weights are positive numbers.u003c/p>nu003cp>But on some graphs weights can be negative — traveling along one segment can offset the cost of traversing another. Consider, for instance, a delivery driver who must balance the cost of gas and tolls (represented by positive weights) against income from transporting packages (represented by negative weights). In such cases, the fastest known shortest-path algorithm doesn’t work. For decades, fast algorithms for finding shortest paths on negative-weight graphs have remained elusive.u003c/p>nu003cdiv id=’component-63c85fc530db7′ class=””>u003cscript type=”text/template”>{“type”:”Article”,”id”:”component-63c85fc530db7″,”data”:{“post”:”id”:115736,”title”:”Researchers Achieve \u2018Absurdly Fast\u2019 Algorithm for Network Flow”,”link”:”https:\/\/www.quantamagazine.org\/researchers-achieve-absurdly-fast-algorithm-for-network-flow-20220608\/”,”date”:”June 8, 2022″,”featured_media_image”:”url”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2022\/06\/Maximum-Flows_520x292.jpg”,”width”:520,”height”:292,”sizes”:”thumbnail”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2022\/06\/Maximum-Flows_520x292-520×292.jpg”,”medium”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2022\/06\/Maximum-Flows_520x292.jpg”,”medium_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2022\/06\/Maximum-Flows_520x292.jpg”,”large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2022\/06\/Maximum-Flows_520x292.jpg”,”square_small”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2022\/06\/Maximum-Flows_520x292-160×160.jpg”,”square_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2022\/06\/Maximum-Flows_520x292-520×292.jpg”,”acf”:”featured_block_title”:””,”featured_image_default”:”ID”:115745,”id”:115745,”title”:”Maximum-Flows_520x292″,”filename”:”Maximum-Flows_520x292.jpg”,”filesize”:63563,”url”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2022\/06\/Maximum-Flows_520x292.jpg”,”link”:”https:\/\/www.quantamagazine.org\/researchers-achieve-absurdly-fast-algorithm-for-network-flow-20220608\/maximum-flows_520x292\/”,”alt”:”Aerial view of a complicated interchange full of flowing traffic”,”author”:”42689″,”description”:””,”caption”:””,”name”:”maximum-flows_520x292″,”status”:”inherit”,”uploaded_to”:115736,”date”:”2022-06-07 20:12:09″,”modified”:”2022-06-07 20:14:18″,”menu_order”:0,”mime_type”:”image\/jpeg”,”type”:”image”,”subtype”:”jpeg”,”icon”:”https:\/\/api.quantamagazine.org\/wp-includes\/images\/media\/default.png”,”width”:520,”height”:292,”sizes”:”thumbnail”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2022\/06\/Maximum-Flows_520x292-520×292.jpg”,”medium”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2022\/06\/Maximum-Flows_520x292.jpg”,”medium_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2022\/06\/Maximum-Flows_520x292.jpg”,”large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2022\/06\/Maximum-Flows_520x292.jpg”,”square_small”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2022\/06\/Maximum-Flows_520x292-160×160.jpg”,”square_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2022\/06\/Maximum-Flows_520x292-520×292.jpg”,”kicker”:”name”:”networks”,”link”:”https:\/\/www.quantamagazine.org\/tag\/networks\/”,”authors”:[]}}u003c/script>u003c/div>nu003cp>Now a trio of computer scientists has solved this long-standing problem. Their new u003ca href=” which finds the shortest paths through a graph from a given “source” node to every other node, nearly matches the speed that positive-weight algorithms achieved so long ago.u003c/p>nu003cp>What’s more, the new approach uses decades-old mathematical techniques, eschewing more sophisticated methods that have dominated modern graph theory research.u003c/p>nu003cp>“I just couldn’t believe such a simple algorithm exists,” said u003ca href=” Probst Gutenbergu003c/a>, a computer scientist at the Swiss Federal Institute of Technology Zurich. “All of it has been there for 40 years. It just took someone to be really clever and determined to make it all work.”u003c/p>nu003ch2>u003cstrong>The Limits of Greedu003c/strong>u003c/h2>nu003cp>The story begins in 1956, when the Dutch computer scientist Edsger Dijkstra developed a fast algorithm to find shortest paths on a graph with only positive weights. To understand it, imagine starting from the source and exploring the graph one node at a time, jotting down the weights of newly discovered edges as you go. Each time you visit a node, make preliminary estimates of the shortest paths from the source to each of the new node’s neighbors, updating any existing estimates if you’ve found a new shorter path. To decide which unexplored node to visit next, use what’s called a greedy strategy: Go to whichever is closest to the source according to your current estimate.u003c/p>nu003cp>With positive weights, the path that Dijkstra’s algorithm takes to visit each node for the first time is truly the shortest. It’s easiest to see that this is true for the very first step. Imagine two nodes A and B connected by an edge with weight 2. If A is the source node, and every other edge touching it has a larger weight, then the direct path from A to B must be the shortest possible path connecting those two points, since the first segment of any other path would already be longer. Similar reasoning works at each step. The algorithm never has to look back, so it’s guaranteed to finish after running through the graph once — that’s what makes it so fast.u003c/p>nu003cdiv id=’component-63c85fc535135′ class=””>u003cscript type=”text/template”>”type”:”Image”,”id”:”component-63c85fc535135″,”data”:”id”:122225,”src”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Desktop.svg”,”alt”:””,”class”:””,”width”:0,”height”:0,”mobileSrc”:”ID”:122224,”id”:122224,”title”:”SHORTEST_PATHS(4)_560-Mobile”,”filename”:”SHORTEST_PATHS4_560-Mobile.svg”,”filesize”:163576,”url”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Mobile.svg”,”link”:”https:\/\/www.quantamagazine.org\/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118\/shortest_paths4_560-mobile\/”,”alt”:””,”author”:”42689″,”description”:””,”caption”:””,”name”:”shortest_paths4_560-mobile”,”status”:”inherit”,”uploaded_to”:122171,”date”:”2023-01-18 15:11:37″,”modified”:”2023-01-18 15:11:37″,”menu_order”:0,”mime_type”:”image\/svg+xml”,”type”:”image”,”subtype”:”svg+xml”,”icon”:”https:\/\/api.quantamagazine.org\/wp-includes\/images\/media\/default.png”,”width”:0,”height”:0,”sizes”:”thumbnail”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Mobile.svg”,”thumbnail-width”:1,”thumbnail-height”:1,”medium”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Mobile.svg”,”medium-width”:1,”medium-height”:1,”medium_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Mobile.svg”,”medium_large-width”:1,”medium_large-height”:1,”large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Mobile.svg”,”large-width”:1,”large-height”:1,”1536×1536″:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Mobile.svg”,”1536×1536-width”:1,”1536×1536-height”:1,”2048×2048″:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Mobile.svg”,”2048×2048-width”:1,”2048×2048-height”:1,”square_small”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Mobile.svg”,”square_small-width”:1,”square_small-height”:1,”square_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Mobile.svg”,”square_large-width”:1,”square_large-height”:1,”zoomSrc”:false,”mobileZoomSrc”:false,”align”:”align=\”inline\””,”wrapper_width”:””,”caption”:””,”attribution”:”u003cp>Merrill Sherman\/Quanta Magazineu003c\/p>\n”,”variant”:”shortcode”,”size”:”wide”,”disableZoom”:false,”disableMobileZoom”:false,”srcImage”:”ID”:122225,”id”:122225,”title”:”SHORTEST_PATHS(4)_560-Desktop”,”filename”:”SHORTEST_PATHS4_560-Desktop.svg”,”filesize”:62881,”url”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Desktop.svg”,”link”:”https:\/\/www.quantamagazine.org\/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118\/shortest_paths4_560-desktop\/”,”alt”:””,”author”:”42689″,”description”:””,”caption”:””,”name”:”shortest_paths4_560-desktop”,”status”:”inherit”,”uploaded_to”:122171,”date”:”2023-01-18 15:11:37″,”modified”:”2023-01-18 15:11:37″,”menu_order”:0,”mime_type”:”image\/svg+xml”,”type”:”image”,”subtype”:”svg+xml”,”icon”:”https:\/\/api.quantamagazine.org\/wp-includes\/images\/media\/default.png”,”width”:0,”height”:0,”sizes”:”thumbnail”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Desktop.svg”,”thumbnail-width”:1,”thumbnail-height”:1,”medium”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Desktop.svg”,”medium-width”:1,”medium-height”:1,”medium_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Desktop.svg”,”medium_large-width”:1,”medium_large-height”:1,”large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Desktop.svg”,”large-width”:1,”large-height”:1,”1536×1536″:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Desktop.svg”,”1536×1536-width”:1,”1536×1536-height”:1,”2048×2048″:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Desktop.svg”,”2048×2048-width”:1,”2048×2048-height”:1,”square_small”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Desktop.svg”,”square_small-width”:1,”square_small-height”:1,”square_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS4_560-Desktop.svg”,”square_large-width”:1,”square_large-height”:1,”largeForPrint”:true,”externalLink”:””,”original_resolution”:falseu003c/script>u003c/div>nu003cp>But negative weights spell trouble for Dijkstra’s greedy strategy. Consider again our delivery driver. A direct route from A to B that nets a small profit may earn less money than a circuitous path that has a big payoff somewhere. “You can’t make decisions just based on the local information,” said u003ca href=” Khannau003c/a>, a computer scientist at the University of Pennsylvania. “You may have to make several seemingly suboptimal moves to finally get a real reward.”u003c/p>nu003cp>For decades, computer scientists working on negative-weight graphs tried to match the speed of Dijkstra’s algorithm with similar “combinatorial” algorithms. These involve discrete operations — like counting possibilities, modifying weights and selectively deleting edges — that reflect the discrete structure of the underlying graph. Progress slowed by the 1990s, however. More recently, researchers have used “continuous optimization” algorithms, which borrow tricks from calculus. Unfortunately, the resulting speedups have been limited, and have often come at the cost of simplicity.u003c/p>nu003ch2>u003cstrong>Break the Cycleu003c/strong>u003c/h2>nu003cp>In the summer of 2021, two computer scientists who’d become colleagues at the University of Copenhagen — u003ca href=” Nanongkaiu003c/a> and u003ca href=” Wulff-Nilsenu003c/a> — were searching for a topic for a joint research project. “Christian said, ‘Oh, by the way, I was on vacation, and because of that I was trying to think of something very ambitious,’” recalled Nanongkai, who’s now at the Max Planck Institute for Informatics in Saarbrucken, Germany. They settled on the negative-weight shortest-paths problem and invited u003ca href=” Bernsteinu003c/a> of Rutgers University to join them.u003c/p>nu003cdiv id=’component-63c85fc535e85′ class=””>u003cscript type=”text/template”>”type”:”Image”,”id”:”component-63c85fc535e85″,”data”:”id”:122196,”src”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/ChristianWulff-Nilsen2013-byDepartmentOfComputerScience-UniversityOfCopenhagen.webp”,”alt”:””,”class”:””,”width”:1279,”height”:1563,”mobileSrc”:false,”zoomSrc”:false,”mobileZoomSrc”:false,”align”:”align=\”right\””,”wrapper_width”:””,”caption”:”u003cp>Christian Wulff-Nilsen was looking for an ambitious problem to tackle with his collaborators. They decided to look for a fast algorithm that could find the shortest paths in a graph with negative weights.u003c\/p>\n”,”attribution”:”u003cp>Department of Computer Science\/University of Copenhagenu003c\/p>\n”,”variant”:”shortcode”,”size”:”default”,”disableZoom”:false,”disableMobileZoom”:false,”srcImage”:”ID”:122196,”id”:122196,”title”:”ChristianWulff-Nilsen2013-byDepartmentOfComputerScience-UniversityOfCopenhagen”,”filename”:”ChristianWulff-Nilsen2013-byDepartmentOfComputerScience-UniversityOfCopenhagen.webp”,”filesize”:360978,”url”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/ChristianWulff-Nilsen2013-byDepartmentOfComputerScience-UniversityOfCopenhagen.webp”,”link”:”https:\/\/www.quantamagazine.org\/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118\/christianwulff-nilsen2013-bydepartmentofcomputerscience-universityofcopenhagen\/”,”alt”:””,”author”:”42689″,”description”:””,”caption”:””,”name”:”christianwulff-nilsen2013-bydepartmentofcomputerscience-universityofcopenhagen”,”status”:”inherit”,”uploaded_to”:122171,”date”:”2023-01-17 21:32:10″,”modified”:”2023-01-17 21:32:10″,”menu_order”:0,”mime_type”:”image\/webp”,”type”:”image”,”subtype”:”webp”,”icon”:”https:\/\/api.quantamagazine.org\/wp-includes\/images\/media\/default.png”,”width”:1279,”height”:1563,”sizes”:”thumbnail”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/ChristianWulff-Nilsen2013-byDepartmentOfComputerScience-UniversityOfCopenhagen-426×520.webp”,”thumbnail-width”:426,”thumbnail-height”:520,”medium”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/ChristianWulff-Nilsen2013-byDepartmentOfComputerScience-UniversityOfCopenhagen.webp”,”medium-width”:1279,”medium-height”:1563,”medium_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/ChristianWulff-Nilsen2013-byDepartmentOfComputerScience-UniversityOfCopenhagen-768×939.webp”,”medium_large-width”:768,”medium_large-height”:939,”large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/ChristianWulff-Nilsen2013-byDepartmentOfComputerScience-UniversityOfCopenhagen.webp”,”large-width”:1279,”large-height”:1563,”1536×1536″:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/ChristianWulff-Nilsen2013-byDepartmentOfComputerScience-UniversityOfCopenhagen-1257×1536.webp”,”1536×1536-width”:1257,”1536×1536-height”:1536,”2048×2048″:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/ChristianWulff-Nilsen2013-byDepartmentOfComputerScience-UniversityOfCopenhagen.webp”,”2048×2048-width”:1279,”2048×2048-height”:1563,”square_small”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/ChristianWulff-Nilsen2013-byDepartmentOfComputerScience-UniversityOfCopenhagen-160×160.webp”,”square_small-width”:160,”square_small-height”:160,”square_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/ChristianWulff-Nilsen2013-byDepartmentOfComputerScience-UniversityOfCopenhagen-520×520.webp”,”square_large-width”:520,”square_large-height”:520,”largeForPrint”:false,”externalLink”:””,”original_resolution”:falseu003c/script>u003c/div>nu003cp>All three researchers were experts in combinatorial graph algorithms for other problems, and they wanted to see how far these relatively ancient approaches could get them. “There’s actually a certain freedom in working on a problem that’s ambitious and has been open for a long time,” Bernstein said.u003c/p>nu003cp>The trio started by temporarily ignoring a subset of possible graphs: those containing negative cycles. These are paths that loop back to where they started after passing through a series of edges whose weights add up to a negative number. In a graph with negative cycles reachable from the starting point, the notion of a shortest path breaks down, since you can make the distance to any node as negative (or as profitable) as you like, by taking repeated laps around the negative cycle before heading off to your destination.u003c/p>nu003cp>The researchers suspected that long negative paths were mainly responsible for making the problem difficult. So they began to focus on tight clusters of nearby nodes, which can’t contain any long negative paths: That’s because if two points are connected by a short positive path, adding a long negative path between them would create a negative cycle. Within a tight cluster, “the fact that everyone is close together in a positive sense actually gives you useful information about the negative edges as well,” Bernstein said. “It tells you things can’t be too negative.”u003c/p>nu003cp>Most graphs contain many such tight-knit clusters that are only weakly connected to each other. If the researchers could pinpoint all the clusters, they suspected they could develop a way to find shortest paths quickly within each one. From there, they might have an easier time connecting individual clusters and finding the shortest paths on the original graph. But that would require quickly spotting the regions of any graph in which nodes are close together — something they didn’t know how to do. The key turned out to be a technique that originated in an entirely different branch of graph theory.u003c/p>nu003ch2>u003cstrong>Cutting Up Graphs   u003c/strong>u003c/h2>nu003cp>In the 1980s, computer scientists developed a technique called low-diameter decomposition to pick out tight clusters in a graph and identify the edges to delete to separate those clusters. This technique provides a way to divide graphs into independent sections. It was invented to facilitate “distributed” algorithms, in which computations run in parallel on different parts of a graph, so it was less obviously useful for shortest-paths algorithms, which don’t have this property.u003c/p>nu003cdiv id=’component-63c85fc539b8c’ class=””>u003cscript type=”text/template”>”type”:”Image”,”id”:”component-63c85fc539b8c”,”data”:”id”:122197,”src”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/DanuponNanongkai2023_byMaxPlanckInstituteForInformatics_2.webp”,”alt”:””,”class”:””,”width”:1150,”height”:1656,”mobileSrc”:false,”zoomSrc”:false,”mobileZoomSrc”:false,”align”:”align=\”right\””,”wrapper_width”:””,”caption”:”u003cp>Danupon Nanongkai helped develop the new algorithm, which finds the shortest paths in a graph by focusing on parts without much negativity.u003c\/p>\n”,”attribution”:”u003cp>Max Planck Institute for Informaticsu003c\/p>\n”,”variant”:”shortcode”,”size”:”default”,”disableZoom”:false,”disableMobileZoom”:false,”srcImage”:”ID”:122197,”id”:122197,”title”:”DanuponNanongkai2023_byMaxPlanckInstituteForInformatics_2″,”filename”:”DanuponNanongkai2023_byMaxPlanckInstituteForInformatics_2.webp”,”filesize”:237818,”url”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/DanuponNanongkai2023_byMaxPlanckInstituteForInformatics_2.webp”,”link”:”https:\/\/www.quantamagazine.org\/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118\/danuponnanongkai2023_bymaxplanckinstituteforinformatics_2\/”,”alt”:””,”author”:”42689″,”description”:””,”caption”:””,”name”:”danuponnanongkai2023_bymaxplanckinstituteforinformatics_2″,”status”:”inherit”,”uploaded_to”:122171,”date”:”2023-01-17 21:32:12″,”modified”:”2023-01-17 21:32:12″,”menu_order”:0,”mime_type”:”image\/webp”,”type”:”image”,”subtype”:”webp”,”icon”:”https:\/\/api.quantamagazine.org\/wp-includes\/images\/media\/default.png”,”width”:1150,”height”:1656,”sizes”:”thumbnail”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/DanuponNanongkai2023_byMaxPlanckInstituteForInformatics_2-361×520.webp”,”thumbnail-width”:361,”thumbnail-height”:520,”medium”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/DanuponNanongkai2023_byMaxPlanckInstituteForInformatics_2.webp”,”medium-width”:1150,”medium-height”:1656,”medium_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/DanuponNanongkai2023_byMaxPlanckInstituteForInformatics_2-768×1106.webp”,”medium_large-width”:768,”medium_large-height”:1106,”large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/DanuponNanongkai2023_byMaxPlanckInstituteForInformatics_2.webp”,”large-width”:1150,”large-height”:1656,”1536×1536″:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/DanuponNanongkai2023_byMaxPlanckInstituteForInformatics_2-1067×1536.webp”,”1536×1536-width”:1067,”1536×1536-height”:1536,”2048×2048″:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/DanuponNanongkai2023_byMaxPlanckInstituteForInformatics_2.webp”,”2048×2048-width”:1150,”2048×2048-height”:1656,”square_small”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/DanuponNanongkai2023_byMaxPlanckInstituteForInformatics_2-160×160.webp”,”square_small-width”:160,”square_small-height”:160,”square_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/DanuponNanongkai2023_byMaxPlanckInstituteForInformatics_2-520×520.webp”,”square_large-width”:520,”square_large-height”:520,”largeForPrint”:false,”externalLink”:””,”original_resolution”:falseu003c/script>u003c/div>nu003cp>Bernstein, Nanongkai and Wulff-Nilsen realized that low-diameter decomposition could help them identify clusters without much concentrated negativity. Unfortunately, standard low-diameter decomposition algorithms only work on undirected graphs — those in which every edge can be traversed in both directions. The negative-weight shortest-paths problem, meanwhile, only makes sense on directed graphs, in which every edge is a one-way street. (Otherwise, a single undirected negative edge would create a negative cycle consisting of repeated hops back and forth across that edge.) If the researchers wanted to use low-diameter decomposition, they’d have to adapt it.u003c/p>nu003cp>That’s what they did in their new paper. Inspired by u003ca href=” worku003c/a> in which Bernstein and Wulff-Nilsen had collaborated with Probst Gutenberg, they developed a fracturing procedure for directed graphs analogous to low-diameter decomposition. The procedure chops up an arbitrary directed graph into a series of tight-knit clusters by using a random process to delete just a handful of edges. Afterward, those clusters are connected by a sparser network in which all the edges point in the same direction. That kind of network is called a directed acyclic graph, or DAG.u003c/p>nu003cp>Think of a DAG like a stream in which water may flow down different paths: Some paths flow in from different sources, others fan out in different directions, and still others may split apart and merge back together. But nothing ever flows backward, so there are no cycles; this makes DAGs much easier to work with.u003c/p>nu003cp>Researchers have long known how to rapidly find shortest paths on DAGs even with negative weights. So the fracturing technique enabled the three researchers to reduce any directed graph to a combination of two special cases — DAGs and tight clusters — that were each easy to handle.u003c/p>nu003cp>The new shortest-paths algorithm repeatedly uses the fracturing procedure to break a graph into tight-knit clusters connected by a DAG. It then breaks those clusters apart further and further. At the end of the process, the clusters at the innermost level are as closely connected as possible. Part of the reason the algorithm is so fast is that it doesn’t take many iterations to fully break down even a very large graph, just as it doesn’t take long to cut a large number down to a reasonable size if you repeatedly divide it in half.u003c/p>nu003cdiv id=’component-63c85fc53fecc’ class=””>u003cscript type=”text/template”>”type”:”Image”,”id”:”component-63c85fc53fecc”,”data”:”id”:122229,”src”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Desktop.svg”,”alt”:””,”class”:””,”width”:0,”height”:0,”mobileSrc”:”ID”:122230,”id”:122230,”title”:”SHORTEST_PATHS(5)_pt2-560-Mobile”,”filename”:”SHORTEST_PATHS5_pt2-560-Mobile.svg”,”filesize”:125702,”url”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Mobile.svg”,”link”:”https:\/\/www.quantamagazine.org\/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118\/shortest_paths5_pt2-560-mobile\/”,”alt”:””,”author”:”42689″,”description”:””,”caption”:””,”name”:”shortest_paths5_pt2-560-mobile”,”status”:”inherit”,”uploaded_to”:122171,”date”:”2023-01-18 15:19:47″,”modified”:”2023-01-18 15:19:47″,”menu_order”:0,”mime_type”:”image\/svg+xml”,”type”:”image”,”subtype”:”svg+xml”,”icon”:”https:\/\/api.quantamagazine.org\/wp-includes\/images\/media\/default.png”,”width”:0,”height”:0,”sizes”:”thumbnail”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Mobile.svg”,”thumbnail-width”:1,”thumbnail-height”:1,”medium”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Mobile.svg”,”medium-width”:1,”medium-height”:1,”medium_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Mobile.svg”,”medium_large-width”:1,”medium_large-height”:1,”large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Mobile.svg”,”large-width”:1,”large-height”:1,”1536×1536″:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Mobile.svg”,”1536×1536-width”:1,”1536×1536-height”:1,”2048×2048″:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Mobile.svg”,”2048×2048-width”:1,”2048×2048-height”:1,”square_small”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Mobile.svg”,”square_small-width”:1,”square_small-height”:1,”square_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Mobile.svg”,”square_large-width”:1,”square_large-height”:1,”zoomSrc”:false,”mobileZoomSrc”:false,”align”:”align=\”inline\””,”wrapper_width”:””,”caption”:””,”attribution”:””,”variant”:”shortcode”,”size”:”default”,”disableZoom”:true,”disableMobileZoom”:false,”srcImage”:”ID”:122229,”id”:122229,”title”:”SHORTEST_PATHS(5)_pt2-560-Desktop”,”filename”:”SHORTEST_PATHS5_pt2-560-Desktop.svg”,”filesize”:56995,”url”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Desktop.svg”,”link”:”https:\/\/www.quantamagazine.org\/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118\/shortest_paths5_pt2-560-desktop\/”,”alt”:””,”author”:”42689″,”description”:””,”caption”:””,”name”:”shortest_paths5_pt2-560-desktop”,”status”:”inherit”,”uploaded_to”:122171,”date”:”2023-01-18 15:19:47″,”modified”:”2023-01-18 15:19:47″,”menu_order”:0,”mime_type”:”image\/svg+xml”,”type”:”image”,”subtype”:”svg+xml”,”icon”:”https:\/\/api.quantamagazine.org\/wp-includes\/images\/media\/default.png”,”width”:0,”height”:0,”sizes”:”thumbnail”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Desktop.svg”,”thumbnail-width”:1,”thumbnail-height”:1,”medium”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Desktop.svg”,”medium-width”:1,”medium-height”:1,”medium_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Desktop.svg”,”medium_large-width”:1,”medium_large-height”:1,”large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Desktop.svg”,”large-width”:1,”large-height”:1,”1536×1536″:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Desktop.svg”,”1536×1536-width”:1,”1536×1536-height”:1,”2048×2048″:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Desktop.svg”,”2048×2048-width”:1,”2048×2048-height”:1,”square_small”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Desktop.svg”,”square_small-width”:1,”square_small-height”:1,”square_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/SHORTEST_PATHS5_pt2-560-Desktop.svg”,”square_large-width”:1,”square_large-height”:1,”largeForPrint”:false,”externalLink”:””,”original_resolution”:falseu003c/script>u003c/div>nu003cp>With the graph fully broken down in this manner, the researchers could quickly find shortest paths through every part of the graph. For the tight clusters at the innermost level of the nested graph structure, this was easy — they had practically no negativity left. And the researchers already knew how to find shortest paths on the DAG sections joining them.u003c/p>nu003cp>Finally, the algorithm adds back the edges eliminated by the fracturing process and calculates their effects on the shortest paths. The researchers proved that their process for randomly deleting edges would almost always require just a few deletions to eliminate “backward” edges — the kind that would turn their DAG into a graph with large cycles. That made it extremely unlikely that any shortest path would pass through too many such backward segments, so they could solve this tricky final step by combining two textbook methods from the 1950s: Dijkstra’s algorithm and the first algorithm developed for negative-weight graphs.u003c/p>nu003cdiv id=’component-63c85fc543050′ class=””>u003cscript type=”text/template”>”type”:”Image”,”id”:”component-63c85fc543050″,”data”:”id”:122227,”src”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/AaronBernstein-CourtesyOfAaronBernstein.2.webp”,”alt”:””,”class”:””,”width”:1235,”height”:1638,”mobileSrc”:false,”zoomSrc”:false,”mobileZoomSrc”:false,”align”:”align=\”right\””,”wrapper_width”:””,”caption”:”u003cp>Aaron Bernstein had worked with Wulff-Nilsen on a previous on a previous problem that involved cutting up graphs. They realized a similar approach might work for the negative-weight shortest-paths problem.u003c\/p>\n”,”attribution”:”u003cp>Courtesy of Aaron Bernsteinu003c\/p>\n”,”variant”:”shortcode”,”size”:”default”,”disableZoom”:false,”disableMobileZoom”:false,”srcImage”:”ID”:122227,”id”:122227,”title”:”AaronBernstein-CourtesyOfAaronBernstein.2″,”filename”:”AaronBernstein-CourtesyOfAaronBernstein.2.webp”,”filesize”:646758,”url”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/AaronBernstein-CourtesyOfAaronBernstein.2.webp”,”link”:”https:\/\/www.quantamagazine.org\/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118\/aaronbernstein-courtesyofaaronbernstein-2\/”,”alt”:””,”author”:”42689″,”description”:””,”caption”:””,”name”:”aaronbernstein-courtesyofaaronbernstein-2″,”status”:”inherit”,”uploaded_to”:122171,”date”:”2023-01-18 15:12:50″,”modified”:”2023-01-18 15:12:50″,”menu_order”:0,”mime_type”:”image\/webp”,”type”:”image”,”subtype”:”webp”,”icon”:”https:\/\/api.quantamagazine.org\/wp-includes\/images\/media\/default.png”,”width”:1235,”height”:1638,”sizes”:”thumbnail”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/AaronBernstein-CourtesyOfAaronBernstein.2-392×520.webp”,”thumbnail-width”:392,”thumbnail-height”:520,”medium”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/AaronBernstein-CourtesyOfAaronBernstein.2.webp”,”medium-width”:1235,”medium-height”:1638,”medium_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/AaronBernstein-CourtesyOfAaronBernstein.2-768×1019.webp”,”medium_large-width”:768,”medium_large-height”:1019,”large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/AaronBernstein-CourtesyOfAaronBernstein.2.webp”,”large-width”:1235,”large-height”:1638,”1536×1536″:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/AaronBernstein-CourtesyOfAaronBernstein.2-1158×1536.webp”,”1536×1536-width”:1158,”1536×1536-height”:1536,”2048×2048″:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/AaronBernstein-CourtesyOfAaronBernstein.2.webp”,”2048×2048-width”:1235,”2048×2048-height”:1638,”square_small”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/AaronBernstein-CourtesyOfAaronBernstein.2-160×160.webp”,”square_small-width”:160,”square_small-height”:160,”square_large”:”https:\/\/d2r55xnwy6nx47.cloudfront.net\/uploads\/2023\/01\/AaronBernstein-CourtesyOfAaronBernstein.2-520×520.webp”,”square_large-width”:520,”square_large-height”:520,”largeForPrint”:false,”externalLink”:””,”original_resolution”:falseu003c/script>u003c/div>nu003cp>“It’s an extremely clever composition of these ideas,” Khanna said. The algorithm is the first for negative-weight graphs that runs in “near-linear” time — which means its runtime is nearly proportional to the time required just to count all the edges, the fastest it could possibly be.u003c/p>nu003cp>And what of the graphs with negative cycles, which the researchers decided to ignore at the start? After putting the finishing touches on their shortest-paths algorithm, they showed that it could also work as a fast algorithm for pinpointing negative cycles. Virtually no graph was beyond its reach.u003c/p>nu003ch2>u003cstrong>Parallel Pathsu003c/strong>u003c/h2>nu003cp>Bernstein presented the team’s result at the 2022 Foundations of Computer Science conference, where their manuscript describing the new algorithm was deemed one of two best papers. The u003ca href=” paperu003c/a> also happened to describe a new near-linear-time algorithm for solving a long-standing problem in graph theory.u003c/p>nu003cp>That algorithm, developed by Probst Gutenberg and five other researchers, addressed a more general problem called minimum-cost flow, in which the goal is to optimize transport through many paths in parallel, and each edge has a maximum capacity as well as an associated cost. Shortest-paths problems are a special case of minimum-cost flow, so the new minimum-cost-flow algorithm could also be used to solve the negative-weight shortest-paths problem in near-linear time, albeit with a radically different approach.u003c/p>nu003cdiv id=’component-63c85fc5436b1′ class=”related-list”>u003cscript type=”text/template”>”type”:”LinkList”,”id”:”component-63c85fc5436b1″,”data”:”title”:”Related:”,”class”:”related-list”,”links”:[“type”:”internal”,”link”:”https:\/\/www.quantamagazine.org\/new-algorithm-breaks-speed-limit-for-solving-linear-equations-20210308\/”,”title”:”New Algorithm Breaks Speed Limit for Solving Linear Equations”,”type”:”internal”,”link”:”https:\/\/www.quantamagazine.org\/elegant-six-page-proof-reveals-the-emergence-of-random-structure-20220425\/”,”title”:”Elegant Six-Page Proof Reveals the Emergence of Random Structure”,”type”:”internal”,”link”:”https:\/\/www.quantamagazine.org\/scant-evidence-of-power-laws-found-in-real-world-networks-20180215\/”,”title”:”Scant Evidence of Power Laws Found in Real-World Networks”]u003c/script>u003c/div>nu003cp>The team working on minimum-cost flow developed their general-purpose fast algorithm using an intricate synthesis of combinatorial and continuous optimization techniques that makes it unwieldy in practice, at least currently. The combinatorial algorithm by Bernstein and his colleagues, though restricted to a more specific problem, achieves its near-linear runtime without sacrificing simplicity.u003c/p>nu003cp>“This is what’s so astonishing about this paper,” said Probst Gutenberg. “You can explain it to an undergraduate student, and you can also implement it on your computer.”u003c/p>nu003cp>As a result, this new algorithm has revived interest in combinatorial approaches to other problems in graph theory. It remains to be seen which problems can be solved rapidly using purely combinatorial algorithms, and which really require the continuous techniques developed in the past 20 years.u003c/p>nu003cp>“This is a philosophical question that I’m trying to understand,” Nanongkai said. “This shortest-path problem gives some hope.”u003c/p>n”,”fadein”:false,”__typename”:”ACFContent”},”$Post:122171.acf.series”:”name”:null,”link”:null,”__typename”:”Term”,”$Post:122171.next.data.0″:”title”:”Mobile Genes From the Mother Shape the Baby’s Microbiome”,”link”:”https://www.quantamagazine.org/mobile-genes-from-the-mother-shape-the-babys-microbiome-20230117/”,”categories”:[“type”:”id”,”generated”:true,”id”:”$Post:122171.next.data.0.categories.0″,”typename”:”Term”,”type”:”id”,”generated”:true,”id”:”$Post:122171.next.data.0.categories.1″,”typename”:”Term”],”featured_media_image”:null,”acf”:”type”:”id”,”generated”:true,”id”:”$Post:122171.next.data.0.acf”,”typename”:”ACFFields”,”__typename”:”Post”,”$Post:122171.next.data.0.categories.0″:”slug”:”abstractions”,”__typename”:”Term”,”$Post:122171.next.data.0.categories.1″:”slug”:”biology”,”__typename”:”Term”,”$Post:122171.next.data.0.acf”:”template”:”article”,”featured_block_title”:””,”featured_image_gif”:false,”featured_image_default”:”type”:”id”,”generated”:true,”id”:”$Post:122171.next.data.0.acf.featured_image_default”,”typename”:”Image”,”featured_image_full_width”:”type”:”id”,”generated”:true,”id”:”$Post:122171.next.data.0.acf.featured_image_full_width”,”typename”:”Image”,”__typename”:”ACFFields”,”$Post:122171.next.data.0.acf.featured_image_default”:”alt”:”Illustration of a mother holding an infant, with strands of DNA running between the bacteria inside them.”,”caption”:””,”url”:” of a mother holding an infant, with strands of DNA running between the bacteria inside them.”,”caption”:””,”url”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2023/01/MaternalMicrobiome-byKristinaArmitage-HP-scaled.webp”,”width”:2560,”height”:1084,”sizes”:”type”:”id”,”generated”:true,”id”:”$Post:122171.next.data.0.acf.featured_image_full_width.sizes”,”typename”:”ImageSizes”,”__typename”:”Image”,”$Post:122171.next.data.0.acf.featured_image_full_width.sizes”:”thumbnail”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2023/01/MaternalMicrobiome-byKristinaArmitage-HP-520×220.webp”,”square_small”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2023/01/MaternalMicrobiome-byKristinaArmitage-HP-160×160.webp”,”square_large”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2023/01/MaternalMicrobiome-byKristinaArmitage-HP-520×520.webp”,”medium”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2023/01/MaternalMicrobiome-byKristinaArmitage-HP-1720×729.webp”,”medium_large”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2023/01/MaternalMicrobiome-byKristinaArmitage-HP-768×325.webp”,”large”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2023/01/MaternalMicrobiome-byKristinaArmitage-HP-scaled.webp”,”__typename”:”ImageSizes”,”$Post:122171.next”:”data”:[“type”:”id”,”generated”:true,”id”:”$Post:122171.next.data.0″,”typename”:”Post”],”__typename”:”PostPageArchive”}n”,”settings”:{“socialLinks”:[“type”:”facebook”,”label”:”Facebook”,”url”:”https://www.facebook.com/QuantaNews”,”__typename”:”SocialMediaLink”,”type”:”twitter”,”label”:”Twitter”,”url”:”https://twitter.com/QuantaMagazine”,”__typename”:”SocialMediaLink”,”type”:”youtube”,”label”:”YouTube”,”url”:”https://www.youtube.com/c/QuantaScienceChannel”,”__typename”:”SocialMediaLink”,”type”:”instagram”,”label”:”Instagram”,”url”:”https://instagram.com/quantamag”,”__typename”:”SocialMediaLink”,”type”:”rss”,”label”:”RSS”,”url”:”https://api.quantamagazine.org/feed/”,”__typename”:”SocialMediaLink”],”newsletterAction”:”https://quantamagazine.us1.list-manage.com/subscribe/post?u=0d6ddf7dc1a0b7297c8e06618&id=f0cb61321c”,”newsletterUrl”:”http://us1.campaign-archive2.com/home/?u=0d6ddf7dc1a0b7297c8e06618&id=f0cb61321c”,”sfNotice”:”An editorially independent publication supported by the Simons Foundation.”,”commentsHeader”:”

n”,”channels”:[{“title”:”The Joy of Why”,”slug”:”the-joy-of-why”,”description”:”The mathematician and author Steven Strogatz interviews leading researchers about the great scientific and mathematical questions of our time.”,”featured_image”:”alt”:””,”caption”:””,”url”:” Science Podcast”,”slug”:”quanta-podcast”,”description”:”Susan Valot narrates in-depth news episodes based on Quanta Magazine‘s articles about mathematics, physics, biology and computer science. “,”featured_image”:”alt”:”A frog leaps out of the frame of the video.”,”caption”:””,”url”:” Joy of x”,”slug”:”the-joy-of-x”,”description”:”The acclaimed mathematician and author Steven Strogatz interviews some of the world’s leading scientists about their lives and work.”,”featured_image”:”alt”:””,”caption”:””,”url”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2022/03/JoX_Spheres_1920x1080-1.jpg”,”width”:1920,”height”:1080,”sizes”:”thumbnail”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2022/03/JoX_Spheres_1920x1080-1-520×293.jpg”,”square_small”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2022/03/JoX_Spheres_1920x1080-1-160×160.jpg”,”square_large”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2022/03/JoX_Spheres_1920x1080-1-520×520.jpg”,”medium”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2022/03/JoX_Spheres_1920x1080-1-1720×968.jpg”,”medium_large”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2022/03/JoX_Spheres_1920x1080-1-768×432.jpg”,”large”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2022/03/JoX_Spheres_1920x1080-1.jpg”,”__typename”:”ImageSizes”,”__typename”:”Image”,”square_image”:”alt”:””,”caption”:””,”url”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2022/03/JofX_podcast_logo-NEW-600.jpg”,”width”:600,”height”:600,”sizes”:”thumbnail”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2022/03/JofX_podcast_logo-NEW-600-520×520.jpg”,”square_small”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2022/03/JofX_podcast_logo-NEW-600-160×160.jpg”,”square_large”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2022/03/JofX_podcast_logo-NEW-600-520×520.jpg”,”medium”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2022/03/JofX_podcast_logo-NEW-600.jpg”,”medium_large”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2022/03/JofX_podcast_logo-NEW-600.jpg”,”large”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2022/03/JofX_podcast_logo-NEW-600.jpg”,”__typename”:”ImageSizes”,”__typename”:”Image”,”subscribe_itunes_link”:”https://podcasts.apple.com/us/podcast/the-joy-of-x/id1495067186″,”subscribe_spotify_link”:”https://open.spotify.com/show/5HcCtKPH5gnOjRiMtTdC07?si=lFzCzat9QfuPU3hWuYibxQ”,”subscribe_android_link”:”https://podcasts.google.com/feed/aHR0cHM6Ly9hcGkucXVhbnRhbWFnYXppbmUub3JnL2ZlZWQvdGhlLWpveS1vZi14Lw”,”subscribe_stitcher_link”:”https://www.stitcher.com/podcast/the-joy-of-x”,”__typename”:”Channel”],”editors”:[“name”:”Bill Andrews – Senior CS Editor”,”__typename”:”Editor”,”name”:”Ben Brubaker – Staff CS Writer”,”__typename”:”Editor”,”name”:”Matt Carlstrom – Senior Engagement Editor”,”__typename”:”Editor”,”name”:”Jordana Cepelewicz – Senior Math Writer”,”__typename”:”Editor”,”name”:”Konstantin Kakaes – Senior Math Editor”,”__typename”:”Editor”,”name”:”Thomas Lin – Editor in Chief”,”__typename”:”Editor”,”name”:”Michael Moyer – Deputy Editor, Physics, Math, CS”,”__typename”:”Editor”,”name”:”John Rennie – Deputy Editor, Biology, Podcasts”,”__typename”:”Editor”,”name”:”Yasemin Saplakoglu – Staff Biology Writer”,”__typename”:”Editor”,”name”:”Samuel Velasco – Art Director”,”__typename”:”Editor”,”name”:”Natalie Wolchover – Senior Physics Editor”,”__typename”:”Editor”,”name”:”Charlie Wood – Staff Physics Writer”,”__typename”:”Editor”],”popularSearches”:[“term”:”math”,”label”:”Mathematics”,”__typename”:”PopularSearch”,”term”:”physics”,”label”:”Physics”,”__typename”:”PopularSearch”,”term”:”black holes”,”label”:”Black Holes”,”__typename”:”PopularSearch”,”term”:”evolution”,”label”:”Evolution”,”__typename”:”PopularSearch”],”searchTopics”:[“type”:”Tag”,”label”:”Podcasts”,”tag”:”name”:”Quanta Podcast”,”slug”:”quanta-podcast”,”term_id”:”552″,”__typename”:”Term”,”category”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”__typename”:”SearchTopic”,”type”:”Tag”,”label”:”Columns”,”tag”:”name”:”Quantized Columns”,”slug”:”quantized”,”term_id”:”551″,”__typename”:”Term”,”category”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”__typename”:”SearchTopic”,”type”:”Series”,”label”:”Series”,”tag”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”category”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”__typename”:”SearchTopic”,”type”:”Category”,”label”:”Interviews”,”tag”:”name”:”Q&A”,”slug”:”qa”,”term_id”:”567″,”__typename”:”Term”,”category”:”name”:”Q&A”,”slug”:”qa”,”term_id”:”176″,”__typename”:”Term”,”__typename”:”SearchTopic”,”type”:”Category”,”label”:”Multimedia”,”tag”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”category”:”name”:”Multimedia”,”slug”:”multimedia”,”term_id”:”43″,”__typename”:”Term”,”__typename”:”SearchTopic”,”type”:”Category”,”label”:”Puzzles”,”tag”:”name”:”puzzles”,”slug”:”puzzles”,”term_id”:”542″,”__typename”:”Term”,”category”:”name”:”Puzzles”,”slug”:”puzzles”,”term_id”:”546″,”__typename”:”Term”,”__typename”:”SearchTopic”,”type”:”Category”,”label”:”Blog Posts”,”tag”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”category”:”name”:”Abstractions blog”,”slug”:”abstractions”,”term_id”:”619″,”__typename”:”Term”,”__typename”:”SearchTopic”,”type”:”news”,”label”:”News Articles”,”tag”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”category”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”__typename”:”SearchTopic”,”type”:”videos”,”label”:”Videos”,”tag”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”category”:”name”:null,”slug”:null,”term_id”:null,”__typename”:”Term”,”__typename”:”SearchTopic”],”searchSections”:[“name”:”Mathematics”,”slug”:”mathematics”,”term_id”:”188″,”__typename”:”Term”,”name”:”Physics”,”slug”:”physics”,”term_id”:”189″,”__typename”:”Term”,”name”:”Biology”,”slug”:”biology”,”term_id”:”191″,”__typename”:”Term”,”name”:”Computer Science”,”slug”:”computer-science”,”term_id”:”190″,”__typename”:”Term”],”searchAuthors”:[“id”:”38171″,”name”:”Adam Becker”,”__typename”:”AuthorList”,”id”:”28087″,”name”:”Adam Mann”,”__typename”:”AuthorList”,”id”:”29794″,”name”:”Alex Kontorovich”,”__typename”:”AuthorList”,”id”:”39302″,”name”:”Alexander Hellemans”,”__typename”:”AuthorList”,”id”:”56″,”name”:”Alla Katsnelson”,”__typename”:”AuthorList”,”id”:”47249″,”name”:”Allison Parshall”,”__typename”:”AuthorList”,”id”:”29458″,”name”:”Allison Whitten”,”__typename”:”AuthorList”,”id”:”73″,”name”:”Amanda Gefter”,”__typename”:”AuthorList”,”id”:”39164″,”name”:”Ana Kova”,”__typename”:”AuthorList”,”id”:”59″,”name”:”Andreas von Bubnoff”,”__typename”:”AuthorList”,”id”:”8728″,”name”:”Anil Ananthaswamy”,”__typename”:”AuthorList”,”id”:”11648″,”name”:”Ann Finkbeiner”,”__typename”:”AuthorList”,”id”:”42689″,”name”:”Annie Melchor”,”__typename”:”AuthorList”,”id”:”95″,”name”:”Ariel Bleicher”,”__typename”:”AuthorList”,”id”:”15493″,”name”:”Ashley Smart”,”__typename”:”AuthorList”,”id”:”450″,”name”:”Ashley Yeager”,”__typename”:”AuthorList”,”id”:”36490″,”name”:”Ben Brubaker”,”__typename”:”AuthorList”,”id”:”16315″,”name”:”Bill Andrews”,”__typename”:”AuthorList”,”id”:”2752″,”name”:”Bob Henderson”,”__typename”:”AuthorList”,”id”:”15492″,”name”:”Brendan Z. Foster”,”__typename”:”AuthorList”,”id”:”68″,”name”:”Brooke Borel”,”__typename”:”AuthorList”,”id”:”62″,”name”:”Carl Zimmer”,”__typename”:”AuthorList”,”id”:”13684″,”name”:”Caroline Lee”,”__typename”:”AuthorList”,”id”:”13691″,”name”:”Caroline Lee”,”__typename”:”AuthorList”,”id”:”50″,”name”:”Carrie Arnold”,”__typename”:”AuthorList”,”id”:”15142″,”name”:”Chanda Prescod-Weinstein”,”__typename”:”AuthorList”,”id”:”8084″,”name”:”Charlie Wood”,”__typename”:”AuthorList”,”id”:”742″,”name”:”Christie Wilcox”,”__typename”:”AuthorList”,”id”:”11543″,”name”:”Claudia Dreifus”,”__typename”:”AuthorList”,”id”:”57″,”name”:”Courtney Humphries”,”__typename”:”AuthorList”,”id”:”7262″,”name”:”Dalmeet Singh Chawla”,”__typename”:”AuthorList”,”id”:”70″,”name”:”Dan Falk”,”__typename”:”AuthorList”,”id”:”19918″,”name”:”Dana Najjar”,”__typename”:”AuthorList”,”id”:”13695″,”name”:”Daniel Garisto”,”__typename”:”AuthorList”,”id”:”32676″,”name”:”Daniel S. Freed”,”__typename”:”AuthorList”,”id”:”13724″,”name”:”David H. Freedman”,”__typename”:”AuthorList”,”id”:”26310″,”name”:”David S. Richeson”,”__typename”:”AuthorList”,”id”:”30207″,”name”:”David Tse”,”__typename”:”AuthorList”,”id”:”19266″,”name”:”Devin Powell”,”__typename”:”AuthorList”,”id”:”13251″,”name”:”Diana Kwon”,”__typename”:”AuthorList”,”id”:”17000″,”name”:”Elena Renken”,”__typename”:”AuthorList”,”id”:”17149″,”name”:”Elizabeth Landau”,”__typename”:”AuthorList”,”id”:”5279″,”name”:”Elizabeth Preston”,”__typename”:”AuthorList”,”id”:”58″,”name”:”Elizabeth Svoboda”,”__typename”:”AuthorList”,”id”:”32612″,”name”:”Ellen Horne”,”__typename”:”AuthorList”,”id”:”27534″,”name”:”Emily Buder”,”__typename”:”AuthorList”,”id”:”25173″,”name”:”Emily Levesque”,”__typename”:”AuthorList”,”id”:”64″,”name”:”Emily Singer”,”__typename”:”AuthorList”,”id”:”47″,”name”:”Erica Klarreich”,”__typename”:”AuthorList”,”id”:”14784″,”name”:”Erika K. Carlson”,”__typename”:”AuthorList”,”id”:”98″,”name”:”Esther Landhuis”,”__typename”:”AuthorList”,”id”:”5830″,”name”:”Eva Silverstein”,”__typename”:”AuthorList”,”id”:”6793″,”name”:”Evelyn Lamb”,”__typename”:”AuthorList”,”id”:”75″,”name”:”Ferris Jabr”,”__typename”:”AuthorList”,”id”:”52″,”name”:”Frank Wilczek”,”__typename”:”AuthorList”,”id”:”69″,”name”:”Gabriel Popkin”,”__typename”:”AuthorList”,”id”:”77″,”name”:”George Musser”,”__typename”:”AuthorList”,”id”:”19092″,”name”:”Grant Sanderson”,”__typename”:”AuthorList”,”id”:”20557″,”name”:”Howard Lee”,”__typename”:”AuthorList”,”id”:”66″,”name”:”Ingrid Daubechies”,”__typename”:”AuthorList”,”id”:”46418″,”name”:”Ingrid Wickelgren”,”__typename”:”AuthorList”,”id”:”85″,”name”:”Ivan Amato”,”__typename”:”AuthorList”,”id”:”37141″,”name”:”Jake Buehler”,”__typename”:”AuthorList”,”id”:”44758″,”name”:”James Dinneen”,”__typename”:”AuthorList”,”id”:”49403″,”name”:”James R. Riordon”,”__typename”:”AuthorList”,”id”:”12170″,”name”:”Janna Levin”,”__typename”:”AuthorList”,”id”:”32″,”name”:”Jeanette Kazmierczak”,”__typename”:”AuthorList”,”id”:”51″,”name”:”Jennifer Ouellette”,”__typename”:”AuthorList”,”id”:”44787″,”name”:”Joanna Thompson”,”__typename”:”AuthorList”,”id”:”72″,”name”:”John Pavlus”,”__typename”:”AuthorList”,”id”:”16475″,”name”:”John Preskill”,”__typename”:”AuthorList”,”id”:”91″,”name”:”John Rennie”,”__typename”:”AuthorList”,”id”:”10351″,”name”:”Jonathan Lambert”,”__typename”:”AuthorList”,”id”:”31716″,”name”:”Jonathan O’Callaghan”,”__typename”:”AuthorList”,”id”:”1241″,”name”:”Jordana Cepelewicz”,”__typename”:”AuthorList”,”id”:”8463″,”name”:”Joshua Roebke”,”__typename”:”AuthorList”,”id”:”49″,”name”:”Joshua Sokol”,”__typename”:”AuthorList”,”id”:”16815″,”name”:”jye”,”__typename”:”AuthorList”,”id”:”67″,”name”:”K.C. Cole”,”__typename”:”AuthorList”,”id”:”37462″,”name”:”Karmela Padavic-Callaghan”,”__typename”:”AuthorList”,”id”:”87″,”name”:”Kat McGowan”,”__typename”:”AuthorList”,”id”:”36139″,”name”:”Katarina Zimmer”,”__typename”:”AuthorList”,”id”:”20556″,”name”:”Katherine Harmon Courage”,”__typename”:”AuthorList”,”id”:”90″,”name”:”Katia Moskvitch”,”__typename”:”AuthorList”,”id”:”39551″,”name”:”Katie McCormick”,”__typename”:”AuthorList”,”id”:”27374″,”name”:”Kelsey Houston-Edwards”,”__typename”:”AuthorList”,”id”:”40″,”name”:”Kevin Hartnett”,”__typename”:”AuthorList”,”id”:”47633″,”name”:”Konstantin Kakaes”,”__typename”:”AuthorList”,”id”:”45758″,”name”:”Kristina Armitage”,”__typename”:”AuthorList”,”id”:”38413″,”name”:”Lakshmi Chandrasekaran”,”__typename”:”AuthorList”,”id”:”12570″,”name”:”Laura Poppick”,”__typename”:”AuthorList”,”id”:”38699″,”name”:”Leila Sloman”,”__typename”:”AuthorList”,”id”:”23451″,”name”:”Liam Drew”,”__typename”:”AuthorList”,”id”:”79″,”name”:”Liz Kruesi”,”__typename”:”AuthorList”,”id”:”38″,”name”:”Lucy Reading-Ikkanda”,”__typename”:”AuthorList”,”id”:”47180″,”name”:”Lyndie Chiou”,”__typename”:”AuthorList”,”id”:”60″,”name”:”Maggie McKee”,”__typename”:”AuthorList”,”id”:”2333″,”name”:”Mallory Locklear”,”__typename”:”AuthorList”,”id”:”3569″,”name”:”Marcus Woo”,”__typename”:”AuthorList”,”id”:”414″,”name”:”Mark Kim-Mulgrew”,”__typename”:”AuthorList”,”id”:”20495″,”name”:”Matt Carlstrom”,”__typename”:”AuthorList”,”id”:”47830″,”name”:”Matt von Hippel”,”__typename”:”AuthorList”,”id”:”17147″,”name”:”Matthew Hutson”,”__typename”:”AuthorList”,”id”:”30953″,”name”:”Max G. Levy”,”__typename”:”AuthorList”,”id”:”32437″,”name”:”Max Kozlov”,”__typename”:”AuthorList”,”id”:”38705″,”name”:”mcho”,”__typename”:”AuthorList”,”id”:”40613″,”name”:”Melanie Mitchell”,”__typename”:”AuthorList”,”id”:”7186″,”name”:”Melinda Wenner Moyer”,”__typename”:”AuthorList”,”id”:”14093″,”name”:”Michael Harris”,”__typename”:”AuthorList”,”id”:”34″,”name”:”Michael Kranz”,”__typename”:”AuthorList”,”id”:”23″,”name”:”Michael Moyer”,”__typename”:”AuthorList”,”id”:”74″,”name”:”Michael Nielsen”,”__typename”:”AuthorList”,”id”:”19093″,”name”:”Michele Bannister”,”__typename”:”AuthorList”,”id”:”1472″,”name”:”Moira Chas”,”__typename”:”AuthorList”,”id”:”6476″,”name”:”Monique Brouillette”,”__typename”:”AuthorList”,”id”:”42264″,”name”:”Mordechai Rorvig”,”__typename”:”AuthorList”,”id”:”10″,”name”:”Natalie Wolchover”,”__typename”:”AuthorList”,”id”:”37605″,”name”:”Nick Thieme”,”__typename”:”AuthorList”,”id”:”43298″,”name”:”Nicole Yunger Halpern”,”__typename”:”AuthorList”,”id”:”37428″,”name”:”Nima Arkani-Hamed”,”__typename”:”AuthorList”,”id”:”19962″,”name”:”Nola Taylor Redd”,”__typename”:”AuthorList”,”id”:”24″,”name”:”Olena Shmahalo”,”__typename”:”AuthorList”,”id”:”1816″,”name”:”Patrick Honner”,”__typename”:”AuthorList”,”id”:”84″,”name”:”Peter Byrne”,”__typename”:”AuthorList”,”id”:”55″,”name”:”Philip Ball”,”__typename”:”AuthorList”,”id”:”31″,”name”:”Pradeep Mutalik”,”__typename”:”AuthorList”,”id”:”24011″,”name”:”Puja Changoiwala”,”__typename”:”AuthorList”,”id”:”100″,”name”:”Quanta Magazine”,”__typename”:”AuthorList”,”id”:”2784″,”name”:”R. Douglas Fields”,”__typename”:”AuthorList”,”id”:”26114″,”name”:”Rachel Crowell”,”__typename”:”AuthorList”,”id”:”9412″,”name”:”Raleigh McElvery”,”__typename”:”AuthorList”,”id”:”820″,”name”:”Ramin Skibba”,”__typename”:”AuthorList”,”id”:”1666″,”name”:”Rebecca Boyle”,”__typename”:”AuthorList”,”id”:”20950″,”name”:”Richard Masland”,”__typename”:”AuthorList”,”id”:”48″,”name”:”Robbert Dijkgraaf”,”__typename”:”AuthorList”,”id”:”80″,”name”:”Roberta Kwok”,”__typename”:”AuthorList”,”id”:”15681″,”name”:”Robin George Andrews”,”__typename”:”AuthorList”,”id”:”24577″,”name”:”Rodrigo Pérez Ortega”,”__typename”:”AuthorList”,”id”:”78″,”name”:”Sabine Hossenfelder”,”__typename”:”AuthorList”,”id”:”23845″,”name”:”Samuel Velasco”,”__typename”:”AuthorList”,”id”:”83″,”name”:”Sarah Lewin”,”__typename”:”AuthorList”,”id”:”35441″,”name”:”Scott Aaronson”,”__typename”:”AuthorList”,”id”:”76″,”name”:”Sean B. Carroll”,”__typename”:”AuthorList”,”id”:”15680″,”name”:”Sean Carroll”,”__typename”:”AuthorList”,”id”:”7239″,”name”:”Shannon Hall”,”__typename”:”AuthorList”,”id”:”44197″,”name”:”Sheon Han”,”__typename”:”AuthorList”,”id”:”65″,”name”:”Siobhan Roberts”,”__typename”:”AuthorList”,”id”:”5944″,”name”:”Sophia Chen”,”__typename”:”AuthorList”,”id”:”61″,”name”:”Steph Yin”,”__typename”:”AuthorList”,”id”:”63″,”name”:”Stephanie Bucklin”,”__typename”:”AuthorList”,”id”:”26311″,”name”:”Stephanie DeMarco”,”__typename”:”AuthorList”,”id”:”71″,”name”:”Stephen Ornes”,”__typename”:”AuthorList”,”id”:”17148″,”name”:”Steve Nadis”,”__typename”:”AuthorList”,”id”:”13356″,”name”:”Steven Strogatz”,”__typename”:”AuthorList”,”id”:”17150″,”name”:”Susan D’Agostino”,”__typename”:”AuthorList”,”id”:”39768″,”name”:”Tamar Lichter Blanks”,”__typename”:”AuthorList”,”id”:”2960″,”name”:”Tara C. Smith”,”__typename”:”AuthorList”,”id”:”14785″,”name”:”Thomas Lewton”,”__typename”:”AuthorList”,”id”:”3″,”name”:”Thomas Lin”,”__typename”:”AuthorList”,”id”:”54″,”name”:”Tim Vernimmen”,”__typename”:”AuthorList”,”id”:”88″,”name”:”Tom Siegfried”,”__typename”:”AuthorList”,”id”:”12964″,”name”:”Vanessa Schipani”,”__typename”:”AuthorList”,”id”:”53″,”name”:”Veronique Greenwood”,”__typename”:”AuthorList”,”id”:”86″,”name”:”Virginia Hughes”,”__typename”:”AuthorList”,”id”:”3244″,”name”:”Viviane Callier”,”__typename”:”AuthorList”,”id”:”89″,”name”:”Wynne Parry”,”__typename”:”AuthorList”,”id”:”15913″,”name”:”XiaoZhi Lim”,”__typename”:”AuthorList”,”id”:”42263″,”name”:”Yasemin Saplakoglu”,”__typename”:”AuthorList”,”id”:”45757″,”name”:”Zack Savitsky”,”__typename”:”AuthorList”],”adBehavior”:”everywhere”,”adUrl”:” Entangled”,”adImageHome”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2021/09/2021PodcastAd_Web-Default_260.jpg”,”adImageArticle”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2021/09/2021PodcastAd_Article_160.jpg”,”adImageTablet”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2021/09/2021PodcastAd_Tablet_890.jpg”,”adImageMobile”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2021/09/2021PodcastAd_Web-Default_260.jpg”,”trackingScripts”:”rnrnrnrnrnrnrnrn”,”theme”:”page”:”accent”:”#ff8600″,”text”:”#1a1a1a”,”background”:”white”,”header”:”type”:”default”,”gradient”:”color”:”white”,”solid”:”primary”:”#1a1a1a”,”secondary”:”#999999″,”hover”:”#ff8600″,”transparent”:”primary”:”white”,”secondary”:”white”,”hover”:”#ff8600″,”redirect”:null,”fallbackImage”:”alt”:””,”caption”:””,”url”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2017/04/default.gif”,”width”:1200,”height”:600,”sizes”:”thumbnail”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2017/04/default-520×260.gif”,”square_small”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2017/04/default-160×160.gif”,”square_large”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2017/04/default-520×520.gif”,”medium”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2017/04/default.gif”,”medium_large”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2017/04/default-768×384.gif”,”large”:”https://d2r55xnwy6nx47.cloudfront.net/uploads/2017/04/default.gif”,”__typename”:”ImageSizes”,”__typename”:”Image”},”modals”:”loginModal”:false,”signUpModal”:false,”forgotPasswordModal”:false,”resetPasswordModal”:false,”lightboxModal”:false,”callback”:null,”props”:null,”podcast”:”id”:null,”playing”:false,”duration”:0,”currentTime”:0,”user”:”loggedIn”:false,”savedArticleIDs”:[],”userEmail”:””,”editor”:false,”comments”:”open”:false,”cookies”:”acceptedCookie”:false},
env:
APP_URL: ‘
NODE_ENV: ‘production’,
WP_URL: ‘
HAS_GOOGLE_ID: true,
HAS_FACEBOOK_ID: true,
,
}

We would like to give thanks to the author of this write-up for this outstanding content

Finally, a Fast Algorithm for Shortest Paths on Negative Graphs | Quanta Magazine

Check out our social media profiles and also other pages related to themhttps://paw6.info/related-pages/