A few days ago I saw several bugs introduced by a well meaning dev who wanted to heed the UIEvent.which deprecation announcement and use the .key property instead. But even if .which is deprecated - that's actually untrue for every browser out there at the moment - the implementation of replacement properties is not fully supported.

First, there is the complication of the effect of the Shift key on the .key property. If you press Shift+3, then .which will be '3' and .key will be '#' and, for Shift-A, 'a' and 'A'. And that happens on a standard United States keyboard layout. For other layouts it's different. There is the concept of a Dead key, which you press on some keyboards to get a character with the press of another key, like adding an accent. In that case the .key property reads 'Dead'!

Second, the .key property is not always there. For example the Edge (and probably Chrome) code to autofill fields is simulating typing (with isTrusted true) without specifying a key. This may not even be a bug, considering that Autofill is not supposed to depend on a specific keyboard.

Then there is a .code property that is supposed to show the physical key that was pressed on the keyboard, but it's only fully implemented in Edge and Safari. And you don't get '1', but 'Digit1' and 'KeyA' instead of 'a' and even stuff like 'Comma'.

And there are other obsolete, deprecated or never fully implemented properties on events: charCode, keyCode, keyIdentifier and so on.

So be careful on how you handle key events. It's a mess.

  One of the things that I can observe nowadays as a 50 year old man is how spam has changed the world, but mostly the people. You see, when the Internet started it was just a random connection between people and sites and any part of that could be abused. It was customary to enter some site or another and be bombarded with flashing ads with shrill grotesque colors. Popup ads came later to great mis-effect. Email was just as unsafe, people having to publish their emails in strange obfuscated ways so that they are not scraped into spam lists. Spam was everywhere and people were not prepared.

  But people learn, so even lacking any real technical or legislative support against spam, the smart kids would train their own brains to detect and ignore spam. An almost The City and the City situation, if you will, where strident portions of your online experience were just automatically scrubbed from perception through training. It's the reason why I find it so hard to see big colorful buttons with icons on them, because my brain is looking for the useful link that says "Download" in text.

  Spam evolved as well, though. Today we are just as spammed as ever, but in more civilized and studied ways. The purpose, after all, is not to curb your enjoyment, but to make you spend your money or your attention. It's just that the latter are much more important for just about everybody but you than the quality of your experience. Emails send you legit subscription content that you can (maybe and with great effort) unsubscribe from. Sites pop up small joyous messages that nudge you to buy something only when you do an action like scroll the page or move to a section of the site. Legitimate looking alerts warn you about the danger you are in and how you could be helped by just spending a bit of money.

  So that leads me to today, when even the visual language of the internet has changed. Every action has to show a little reaction, a shading, a rotation, a spark, party poppers, shining stars, animated people and animals emoting to your every gesture. And it only gets worse from there.

  And I am asking myself: how do these sites survive? Surely people open them and their brain shouts SPAM!!! in panic and they close the site, right? Well, no. Apparently, people raised on this stuff got addicted to it. A "normal" site with text and images and links feels bland and uninspiring to them. They NEED the feedback and continuous stimulation. My youth spent in the wild early Internet has created imune responses that just fire up regularly today for things that younger generations feel its completely normal.

  I am not here to argue who is right and why, but just to note how this online experience - like any other experience - changes us without our conscious awareness, in directions that takes a lot of time and self reflection to even perceive. To paraphrase Trainspotting: We are colonised by spam. We can't even pick a decent, vibrant, healthy thing to be colonised by. No. What does that make us?

  The Witch and the Tsar started intriguing, with Baba Yaga being the protagonist of the story, but within one chapter it became obvious it was some kind of weird misandrist fantasy instead of a well rounded story. I won't read this.

  The Loop has almost everything that is good about young adult books, but also all of the bad.

  Ben Oliver starts with a somewhat silly idea, derivative from The Matrix, where people can be used as batteries, describes an endless prison of death row inmates that get to delay their sentence every now and then by accepting being guinea pigs for an extension of their life and controlled by a combination of heartless psychopaths and undefeatable technology. So far so good.

  Then he presents cardboard shallow characters that are inconsistent, dimwitted and bland and asks us to care about anything that happens to them. And of course this crap is part of a trilogy! He leaves literal (Chekov's?) weapons lying around and people too dumb to remember they were there to begin with. Ugh!

  As for the author, the only contact for a Ben Oliver I could find was a twitter account that has since been closed.

  When you dump every cliché of YA novels, then refuse to follow up with any of reason, adventure or empathetic characters, all you have is a flashy Apple TV like story, with a lot of form and no substance. I tried and tried to finish it reading it, but I gave up halfway. DNF this thing!

  I have no idea why I put Darius The Great Is Not Okay on my reading list. It's a short introspective book about a young Iranian-American boy going for the first time in Iran to meet his mother's family. It's coming of age, deals with clinical depression and it's pretty sweet. But that's about it.

  The guy is a Trekkie - The Next Generation no less - and peppers the book with references, so that was fun, but I guess if you are not most of them will fall flat. Funny enough, just before that I was reading a book about a Jewish girl, but I swear I chose the books at random.

  Anyway, I did enjoy the Persian culture references, which I think it's the best part. Darius himself is a rather dull character: young boy who believes people think badly of him and that he's not enough and then magically grows into a person because he gets some support and understanding from the Iranian part of his family and finally makes a friend. And no, there is no magic, this is a straight book, mostly autobiographical.

  Adib Khorram's writing is good, but almost like reporting. I didn't really feel as things flowed in a literary sense. I did enjoy it, but I can't recommend it, unless you're into this kind of stuff.

Laziness is priced in

  When I was a kid, playing with Windows 3.11, I quickly found out that network drive sharing was on by default. This means that anyone on your local network could read almost any file in your C: drive unless you did something about it. And also, all of your passwords - including the user and password of your Internet connection - were saved into a single file that was poorly encrypted, so that meant that anyone in your local network, with a silly little program that would crack that file in minutes, could have all of your passwords.

  But I wasn't "a hacker" knowing this anymore than a person would be a thief if they found some money on the ground. Why would the premier operating system on the planet be this dumb? Well, the answer was simple: people didn't really do local networks in the age of the modem, people didn't read the technical documentation of operating systems like I did and people weren't aware of what would be going on to complain about it even if it happened. In reality, anyone connecting to any ISP would have their user and password visible to any other person connecting there. Not only that, but any and all personal files on their computer.

  I like to call this "the price of laziness". If it apparently costs more to fix than to ignore, it will never get fixed. This particular issue was trivial to be solved by any ISP, they just chose not to.

  Remember movies like Hackers or WarGames, where kids were routinely entering secure systems to the chagrin of "the man"? It wasn't because they were smart and cool like in the movies, it was because no one was bothering to protect their clients. Did you know that for more than 20 years the nuclear safety codes for U.S. rockets was 00000000? When something awful happens to you and people knew about the cause of your problem way before you had it, it means just that not enough consequential people had that problem before you that someone would be bothered to fix it.

  And now, when I am NOT a kid, I see the same stupid stuff. The official YouTube TV application is punishing me for every video with tens of seconds of ads every time I start one and sometimes smack in its middle anyway. But if you close the video two or three times, it just goes through. This only means they calculated the price of the average person watching videos pressing Back and OK a few times is larger than the price it takes them to passively endure minutes of ads.

  One might say that in this case everybody's happy: Google reports people have watched the ads, smart people get around them, lazy people don't, money flows. But there are people who are paying for those ads to be displayed and even if I find no real sympathy for them, their service provider should!

  Same thing with JavaScript paywalls on major news websites. You open one article or two and they slap you with "You've read the last free article for today". Or... you could just disable JavaScript for the site and read ALL of their articles. And I know there is a feeling of smugness when you do this, but again, it was right there. No one actually cared enough to prevent you to read the article! The SEO score was more important. Most people are paying.

  Piracy is the perfect example. There are today simple ways of watching any movie or series, listening to any song, reading any book, without paying a dime. And while authors are crying about it, no one actually does anything because most people find those ways more complicated than paying tens of dollars monthly for streaming services. Streaming services that will increase the price or bring back ads for the cheap tiers or cancel any show as long as they got people excited enough to subscribe to the service with the first season and so on. There was a time when streaming was considered "the solution to piracy" because piracy dropped sharply once people had a comfortable experience devoid of guilt and priced reasonably. But piracy went back up, because the price did not stay reasonable and the experience got increasingly less comfortable as corporations felt they had you locked in.

  In all the companies I worked for as a software developer, I was routinely denied when trying to fix bugs if "it wasn't planned". So when you use some software or app or web site and it fails in the most stupid ways, remember to not curse the developers, they actually wanted to solve those issues, in their free time, and were denied because there was no money in it!

And then they blame you

  This post is not about software or the Internet, it's about everything! The curse of "Good enough" is what led us to this. The laws that only work for some, the way everything seems to get more and more complicated by the day for no reason, the "security" that everyone shoves does your throat even if you don't want it, because they need your data or identity or shopping patterns, the sad predatory state of human relations. Ah, it's good enough! What could possibly go wrong?

  But it gets worse. When people inevitably start taking advantage of these blatant holes, the answer of the authorities is to heavily punish the people that do it rather than the people that leave those in. That's why when I was a kid I could find tons of documentation on how to do all kind of fun stuff in libraries maintained by groups of dedicated people, but then you just couldn't, because it had become very very illegal. That meant that yes, it was harder to find the simple ways in which you could circumvent systems, but also that it was a lot harder to train to harden systems. If you meet security experts nowadays, they are all paranoid as fuck, not only because they know how easy it is to get somewhere and cause harm, but of how random and stupid authorities treat people with such knowledge.

  It had become routine for companies that are approached by people who found security holes in their systems to sue them for hacking, rather than thank them, reward them and fix the hole. And even if it's evil, it's also partially understandable, because in the idiotic legal systems of today, rewarding someone for finding a security hole means admitting you had one, so you can be sued!

  If Hackers and WarGames were pure entertaining fantasies, something like Takedown - also heavily dramatized - is closer to the truth. There is a scene where the hacker laments that he could do any number of evil deeds, crash systems, steal millions, but he choses not to, yet all law enforcement is after him. Ironically, the movie is based on the demonstrably self-aggrandizing book written by the guy who caught Kevin Mitnick, not on Kevin Mitnick's book.

Other thoughts

  I wrote this post because I remembered the Takedown movie, perhaps Skeet Ulrich's best role ever. Mitnick was a slightly annoying personality for me, but I was sad to hear he died of pancreatic cancer three years ago.

  For a long time I thought of how to create a web site that would allow people to pay for what they stole, if that thing turned to be as good as advertised and people would afford it. For example you would download a movie off the Internet, watch it, enjoy it, then go and pay the company anything for the movie. If someone would get to sue you for pirating content, you could use proof of that payment to justify a reduced punishment. But of course it wouldn't work. Who would be stupid enough to declare they have stolen something knowing full well that some asshole would find a way to use that against them?

  But maybe it would work as a kind of donation system, a delayed Kickstarter, where you just send a tip of appreciation to authors. But it doesn't work like that, either. You would want to send the money to the author of the book you liked, not to the publishing house which essentially owns the book. They would immediately find a way to stop or leech off the money you send like that.

  And final nail in the coffin (quoting ChatGPT here) "Financial systems generally require consent and identification on the recipient side. There’s no standard “send money to this person by name only” system for privacy, fraud, and compliance reasons."

  In conclusion, you pay for "just good enough" and get worse, you are villainized for finding ways to abuse that, even if you don't actually use them and report them for fixing and trying to retroactively fix/pay for your abuse doesn't work either. Meanwhile anything better than "good enough" is altered to be more expensive until it becomes "good enough for what I am paying". Some might call it equilibrium of demand and offer, I call it paying to stay lazy.

Intro

I am sure you have heard of Universal Basic Income (UBI), the idea that every citizen should receive a monthly payment, regardless of any employment, effort or role in society. For obvious reasons, it has its detractors, but also it represents a simple and equitable way of providing to even the poorest of us.

I don't want to get into UBI itself, there are a lot of smarter people debating it, but the discussions about it flare up every time new developments in automation happen. If people are replaced by Artificial Intelligence (AI) and robots, then it's easier to imagine a post scarcity civilization where machines do the work and humans enjoy the rewards. Human nature, though, makes this hard to conceive.

But what if ubiquitous AI and robots logically lead to the same ultimate outcome regardless?

The shareholder market

In today's Western capitalism it's common to invest in shares or other financial instruments which abstract participation in wealth creation. Instead of creating your own business, working for one or partnering with someone for one, you just buy a piece of an existing business and you get to own a part of its future profits, if any. What does this sound like to you? There is a non-human entity - the business - that does the work and you - the human - enjoy the rewards.

Now imagine you have an AI that you run from home. You install it on your computer and you give it access, configure some skills, give it some money, then tell it to make more of it. You will own its future profits, if any. It's exactly the same thing.

With smart machines, what we now call "passive income" is the only type of income we will get to have.

AI capital

Running the hypothetical AI to generate profits makes you a shareholder in the AI. As long as you own a computing device and have the resources to run a truly intelligent AI on it, you don't have to work anymore.

You don't need to run the AI yourself, you can buy shares from the company that does run it, or you can split the ownership between multiple people. It then gets complicated when any of those people may be themselves artificial. It leads to an interconnected network of people and machines, ownership, control and work that has only one purpose: reduce human effort and maximize returns.

This is just UBI with a different name. Instead of society assigning everyone a piece of the pie, some other entity does it, an AI, a company, a corporation, a group, a relative, another machine, and so on. To me this is the logical, almost inevitable, outcome. Have you ever heard the proverb "Give a man a fish, and you feed him for a day. Teach a man to fish, and you feed him for a lifetime." ? Now imagine its corporate version: "Give a man a fish, and you feed him for a day. Give a man a share of a fishing business, and it feeds him for a lifetime."

And yes, some people will have more and some people will have a lot less, but when the entire thing dwarfs human scale and understanding, it will not matter that much.

The end

I've written a lot more on this until I decided to delete it. But you can take this idea further for yourself. In a sense, eternal heaven feels almost inevitable, but at the same time there is nothing for people to do in it anymore - it's also hell. You will get tired of games, cyclical fashion and never ending sexual orgies soon enough. Disease, aging and maybe even death will lose all meaning. We will get worlds of our own where we can do anything we choose.

The funniest thing of all this is that the same mechanisms that make some people want to take control from you, own you, grab everything for themselves are the ones that will slow this process down. Maybe before we all get there, some asshole is going to blow it all up out of spite or incompetence. There will be people who will not get to control any resource generating machine and have no say in what happens. Their suffering will stain our legacy forever, give us another round of strong feeling, meaning and direction, but ultimately it will slightly slow down the final result.

Just like we toil today in thankless workplaces just to make ends meet, then get home to some animal that is ecstatic to see us and will make us smile and give us a sense of meaning, I think machines will take that role, leaving us the only remaining option: being the pet.

  I can't say anything really bad about The World That We Knew. The writing is very good, the characters interesting, but I couldn't find the will to continue reading the book. I may be retrying later, when the zeitgeist is different.

  One problem with the book is that is another story about Jews being oppressed by the evil German Nazis, and at this time I found difficult to separate that idea from the things happening right now. Rather than try to avoid resolving that internal conflict, I've decided to postpone.

  A rather more relevant problem is that... other than the presence of a golem, the story is hardly fantasy, at least up to the point where I stopped reading. One could just as well not make it fantasy and just write a regular historical fiction set in WWII.

  Bottom line: slight chance to try again much later.

  What a delightful dark Icelandic folklore inspired fantasy! If you liked the Arcane animated series, Shadows of the Short Days feels just like that. Young revolutionary young women who go too far, mad knowledge obsessed geeks who go too far, fascist governments with crazy magical steampunk SS corps going too far, and dark and depressing, as any good Nordic writing has to be. The writing of Alexander Dan Vilhjálmsson is good, the world building really detailed, I loved it!

  One thing I didn't like was the info dump at the beginning of the book, a bit like the Irulan presentation in the beginning of Lynch's Dune film, which made me think it was also mandated from up high so that the book doesn't put off the normies. It introduces some sort of space colonization story that doesn't really fit with the rest of the book, for starters.

  Another thing that was hard to swallow were the characters. They were very well written, but all of them were selfish delusional assholes. Hard to truly root for any of them.

  But the story was amazing and I lapped it up. An alternate world Reykjavík where magic of two types is real, magical creatures are real and the human government oppresses everything not human, especially the halflings. One of the protagonists is one such halfling, a young woman determined to start a revolution for equality and freedom and ready to walk over corpses to achieve her goal. The second is a student of magic, expelled by the unimaginative authorities of the university, and willing to do anything to understand and tap into the source of magic. They attract the attention of the sadistic government magicians who will, of course, also do anything to achieve their goals.

  Needless to say, things don't really go great for anybody involved. In a world where you can drink or take drugs to alter your magical abilities, not even these sure way solutions to relax and chill the hell down can work.

  Bottom line: it was a very exciting book to read and I intend to continue the series, although not right now. It was actually taxing to live through it and the ending was quite satisfactory. Honestly, this doesn't need a continuation, even if I am glad there is one.

  I couldn't even get through the beginning. If you like the servant girl who becomes magically amazing while caught in some kind of love triangle trope, you're in luck: it's a pentagon! I however, don't like this kind of stuff and I really didn't like the writing style either.

  Bottom line: I DNFed Power of Five, by Alex Lidell. Couldn't find a website or wiki entry for her, either, which I assume means it was probably a good decision.

  The beginning of Gideon the Ninth is very exciting: a world of necromancers locked in apparent eternal decay, served by undead skeletons that just barely maintain the status quo. Powerful magicians living in crumbling crypts and eating slop. I honestly thought it was some subtle jibe regarding AI.

  However, this quickly turns into a completely different genre: an escape room/whodunnit that also reveals the scale of the "universe" is incredibly small. Something cataclysmic happened to people, if these are even people, and no one seems to be aware of it, locked in ridiculous feudal relationships in a tiny empire. What's going on?!

  Unfortunately, Tamsyn Muir doesn't really explain that at all, instead focusing on the sister-like rivalry between the main protagonists, with the obligatory lesbian romance undertones that are thankfully not explored, since it would have meant nothing in this particular story context.

  Bottom line: a really intriguing start, leading to an unexplainably shallow world with a plot that was frankly ridiculous in any setting. I liked the characters quite a lot, but the story was absurd. I liked reading it, but I will not continue the series and I can't recommend it.

  I was quite surprised that this fantasy story, heavily influenced by Chinese folklore, is actually not written by a Chinese author. While the structure is predictable, with vibes of Harry Potter, the premise and execution, as well as the context, are extremely intriguing and exciting. I intend to read the rest of the books!

  In Unsouled, a fertile valley is populated by various clans which live in a feudal equilibrium, where they are not at war, but they are eternal enemies. Families inside each clan vie against each other as well, trying to gain status within the clan. Magic is a thing and for every child a test is performed to determine what kind of soul they possess: Enforcers, Strikers, Rulers and Forgers, which will then determine their role in society. Extremely rarely, the test fails, relegating the tested to the status of Unsouled. Obviously, the main character is such a one.

  Will Wight does a wonderful job in creating the characters, their motivations, building the world and then expanding it to a ridiculous degree. I was immediately curious on what will happen and wanted to continue to read the series, which is what I intend to do. In this first book, the temporary stigma of being an Unsouled is being partially overcome, but without solving the underlying problem of having no training or usable skills. Also, really heavy stakes increase the motivation for the character to grow.

  If I were to criticize something, it's the cunning that the character demonstrates, which seems to belong solely to him. The rest of the people, including masters of magic and figures of authority, seem to be complete idiots most of the time, which diminishes the accomplishments of the hero. Overall, though, a really refreshing book.

  Will Jordan is the real name of Critical Drinker, a famous critic on YouTube that I enjoy watching, although not always agree with. So when I heard he was an author, too, I've decided to read his first book, Redemption, the first in a series of spy action novels starring Ryan Drake. Let's get into it, shall we?

  Well, nothing to say, really. It's a completely average spy action thing, the kind of novel you buy in an airport to read during the flight and never think about it again. Ryan Drake is an aging, almost retired CIA agent, he's recruited to save a mysterious woman from a Russian prison in order to solve a much bigger problem. Obviously, the woman is also incredibly competent, attractive and quick to become a love interest. Weird rivalries, old conflicts, twists and double crosses and international travel while targeted by everybody, they all feature in this classically conceived story.

  I can't say anything about the style of writing either. The beginning is filled with superfluous adjectives and adverbs, like every first book, but then the author finds his pace and starts writing like a human being, but nothing spectacular.

  The major criticism that I have is that the stakes, presented at the start and very real and exciting, have almost no impact on the rest of the book. The most interesting part of the story is relegated to a MacGuffin, only to focus on the very ordinary actions and emotions of the various characters. Also, while the book explains why some things that should have been impossible end up happening anyway, this gives away a lot of the final twists if you just bother to think it through. The overly optimistic ending has some internal contradictions that I won't go into because it would spoil the plot.

  It was easy to read and mildly entertaining. I am sure that Jordan will have done better in the next eight books in the series, but as it is, this first one doesn't motivate me to read them. Was briefly tempted to try out his latest book, Dark Harvest, which is a zombie action thriller, but when I started reading the reviews, seems to be kind of the same thing: cold war era stuff, gulf war era stuff, soldiers and action, romance between soldiers and doctors and a zombie virus related to the Dyatlov Pass, mostly as an afterthought.

  Bottom line: the author has his three act plot structure down, but then he has to write something that is actually exciting and original, which seems more difficult for him. This book in particular is his first, so forgive any amateurisms, but even if it were phenomenal, the story remains a classic spy thriller that ultimately means nothing.

  You know when you are trying to finish a book and you don't really enjoy it, but you feel you own it to the author to at least finish it before you review it? That's what Station Eternity was to me. And because of that feeling, I stopped reading anything for a few months. Which is a lot. Finally, I've decided it wasn't worth it and DNFed it.

  The premise is intriguing: a human apparently cursed to cause murders to happen around her and then be the one to solve the murder. Like an involuntary Jane Marple. So she just has to get away from people on an alien space station, home to all kinds of weird and interesting species. So what happens when a shuttle full of humans is approaching the station?

  The execution was terrible, for me at least. It's not that Mur Lafferty's style is bad, it's just that she focuses on ideas and details that I find absolutely uninteresting. There are some other books that gave me a similar vibe, where things happen in space during some major crisis, but the focus is not on the science or the conflict, but on the romantic interests and random feelings of the characters. This is not quite like as bad, but it's close.

  Bottom line:  I couldn't hate the book, but I couldn't like it either, so I just decided to read other stuff.

  P.S. I am a fan (although not a frequent consumer) of Escape Pod, Pseudopod and PodCastle, with which the author is/was affiliated. If that connection would have been relevant, I would have praised the book more, but obviously, that's not the case. Those podcasts are cool, though, and completely free!

Intro

  At the moment I am looking for a job, so in my research into coding test platforms, the problems that cannot be solved with just a little thinking and some loops are 80% covered by just 8 categories of problems:

1. Optimization with overlapping subproblems (coin change, longest increasing subsequence, knapsack variants, matrix chain) - solved with Dynamic Programming (memoization/tabulation).
2. Pathfinding, connectivity, or level-order processing in grids/graphs (number of islands, shortest path in maze, rotten oranges) - solved with Graph Traversal: BFS and DFS.
3. Hierarchical data processing (tree diameter, in order traversal, BST validation, lowest common ancestor) - solved with Tree Traversals and Properties (pre/in/post-order, level-order, recursion/DFS on trees).
4. Exhaustive search with pruning (permutations, subsets, N-Queens, sudoku solver, word search) - solved with Backtracking.
5. Local optimal choices that work globally (jump game, task scheduler, fractional knapsack) - solved by Greedy Algorithms.
6. Efficient "top-k" or priority processing (merge k sorted lists, kth largest element, task scheduler with cooldown) - solved with Heaps / Priority Queues.
7. Efficient union of sets / cycle detection in graphs (redundant connection, number of provinces, Kruskal's MST) - solved with Union-Find (Disjoint Set Union) with path compression & union-by-rank.
8. Searching in sorted/monotonic spaces (search in rotated sorted array, minimum in rotated array, binary search on answer for capacity problems) - solved by Binary Search (advanced variants).

Bonus:

• Efficient prefix and pattern matching - solved by Trie and KMP String Search 
• Efficient range queries and updates - solved by Segment Tree and Fenwick Tree
• Shortest paths with negative weights and all-pairs - solved by Bellman-Ford and Floyd-Warshall

This post will be about shortest path problems when the weights may be negative: Bellman-Ford and Floyd-Warshall.

When to use

Dijkstra (see the Heaps post) is fantastic when all weights are non-negative, but as soon as negative edge weights appear (currency arbitrage, flight prices with refunds, or certain graph modeling tricks) Dijkstra fails.  

Bellman-Ford solves the single-source shortest path problem with negatives and can detect negative cycles.

• single source, possible negative edges, need to detect negative cycles (O(V·E) is acceptable).

Floyd-Warshall solves the all-pairs shortest path problem in one shot and also detects negative cycles.

• dense graph (E ≈ V²), need distances between every pair of nodes, V ≤ 400 (O(V³) is fine).

Typical problems: cheapest flights with refunds, arbitrage detection, transitive closure, "find the city with the smallest number of reachable neighbors within a distance threshold".

Theory

Relaxing an edge means that if the path from source to a destination node is shorter if doing it via an intermediate node, we update the estimate for the distance from source to destination. The term comes from the fact that the distance to a node is an upper bound (a "relaxed" estimate) on the true shortest-path distance. When we find a better path, we relax (lower) that upper bound. The operation never increases the estimate, and after enough relaxations the estimates become exact shortest-path distances.

Bellman–Ford, Dijkstra, A*, Johnson's algorithm and others use edge relaxing. 

Bellman-Ford

The core idea of the algorithm is to relax every edge |V|−1 times. After that, any further relaxation means a negative cycle exists.

Implementation:

int[] ShortestPath(int n, int[][] edges, int src)
{
    const int halfMax = int.MaxValue / 2;
    int[] dist = new int[n];
    Array.Fill(dist, halfMax);
    dist[src] = 0;

    // Relax |V|-1 times
    for (int i = 0; i < n - 1; i++)
    {
        foreach (var e in edges)
        {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != halfMax && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }

    // Check for negative cycle
    foreach (var e in edges)
    {
        int u = e[0], v = e[1], w = e[2];
        if (dist[u] != halfMax && dist[u] + w < dist[v])
            return null; // negative cycle reachable from src
    }

    return dist;
}

int[][] edges = [
    [0, 1, 5],
    [1, 2, -3],
    [0, 2, 10]
];

var dist = ShortestPath(3, edges, 0);

Console.WriteLine(dist != null
    ? string.Join(", ", dist)   // 0, 5, 2
    : "Negative cycle detected");

Complexity

• Time: O(V*E)
• Space: O(V)

The O(V*E) time bound follows directly from |V| passes over the edge list, and the space is O(|V|). In practice the algorithm often converges early (no updates in a pass), but the worst-case analysis guarantees correctness even on adversarial inputs with negatives. This combination of dynamic-programming clarity, negative-weight tolerance, and built-in cycle detection makes Bellman-Ford the theoretical foundation for many more advanced shortest-path algorithms (Johnson’s algorithm, difference constraints, etc.).

The Bellman-Ford algorithm solves the single-source shortest-paths problem on a directed graph by exploiting the optimal substructure of shortest paths via dynamic programming. After the k-th iteration, every distance value in the array is already the shortest possible path from the source that uses at most k edges.

Each full pass over every edge checks whether there is a better way to reach any node by coming through one additional edge. Because the previous pass already had the best answers using up to k-1 edges, this new pass simply improves the answer to the best version that now allows one more edge.

A simple path in a graph can never use more than n-1 edges; if it did, it would have to visit the same node twice and therefore contain a cycle. That means after exactly n-1 complete passes, the array already holds the true shortest paths from the source to every reachable node, provided there are no negative cycles.

One final extra pass is then performed. If any distance can still be made smaller, it means there must be a negative cycle reachable from the source, because otherwise the distances would already be optimal and no further improvement would be possible. This extra check is what gives Bellman-Ford its ability to detect negative cycles, something Dijkstra cannot do.

Floyd-Warshall - shortest path

Floyd-Warshall starts with a table that only knows the direct edges between every pair of nodes (infinity for no connection). Then it goes through every possible intermediate node, one by one, and for every possible pair of start and end nodes it updates the table if the path through there becomes shorter.

Here is the implementation:

int[][] AllPairsShortestPath(int n, int[][] edges)
{
    const int halfMax = int.MaxValue / 2;
    var dist = new int[n][];
    for (var i = 0; i < n; i++)
    {
        dist[i] = new int[n];
        Array.Fill(dist[i], halfMax);
        dist[i][i] = 0;
    }

    foreach (var e in edges)
    {
        int u = e[0], v = e[1], w = e[2];
        dist[u][v] = Math.Min(dist[u][v], w);
    }

    for (var k = 0; k < n; k++)
        for (var i = 0; i < n; i++)
            for (var j = 0; j < n; j++)
                if (dist[i][k] != halfMax && dist[k][j] != halfMax)
                    dist[i][j] = Math.Min(dist[i][j], dist[i][k] + dist[k][j]);

    // Negative cycle check
    for (var i = 0; i < n; i++)
        if (dist[i][i] < 0)
            return null;

    return dist;
}

int[][] edges = [
    [0, 1, 5],
    [1, 2, -3],
    [0, 2, 10]
];

var distMatrix = AllPairsShortestPath(3, edges);
Console.WriteLine("0 -> 2: " + distMatrix[0][2]); // 2

Complexity

• Time: O(V³)
• Space: O(V²)

The Floyd-Warshall algorithm solves the all-pairs shortest-paths problem on a directed graph by using dynamic programming to consider every possible intermediate node in a systematic way. It begins with a distance table that contains only the direct edge weights between every pair of nodes. Then, for each potential stopping point in the graph, it checks every possible pair of start and end nodes and updates the recorded distance if routing through that stopping point produces a shorter total path.

Because it exhaustively tries every possible intermediate node exactly once, and does so in an order that builds upon previously discovered shorter routes, the final table contains the true shortest path between every pair of nodes, assuming no negative cycles exist. An extra check at the end looks for any negative values on the diagonal of the table to detect whether a negative cycle is present anywhere in the graph. This triple-loop approach is simple , turning what would be many separate single-source problems into a single computation.

Comparison

Best for

• Bellman-Ford: Single source, sparse graphs
• Floyd-Warshall: All-pairs, dense graphs (V≤400)

Detects negative cycles

• Bellman-Ford: Yes (reachable from source)
• Floyd-Warshall: Yes (anywhere in graph)

Time

• Bellman-Ford: O(V*E)
• Floyd-Warshall: O(V³)

Space

• Bellman-Ford: O(V)
• Floyd-Warshall: O(V²)

Typical problems:

• Bellman-Ford: Cheapest Flights variants, arbitrage
• Floyd-Warshall: City with smallest number of neighbors within distance., Evaluate division (variants), transitive closure

Code simplicity

• Bellman-Ford: Medium (edge list)
• Floyd-Warshall: Very simple (matrix)

Notes

• Dijkstra is faster when no negatives
• For Bellman-Ford, early termination after no updates in a pass is a nice optimization (still O(V*E) worst case).
• Floyd-Warshall is perfect when V ≤ 400; beyond that you usually need Johnson’s algorithm (Bellman-Ford + Dijkstra).
• Negative cycle detection: Bellman-Ford only detects cycles reachable from the source; Floyd-Warshall catches any cycle in the graph.
• Edge cases: self-loops, disconnected components, negative self-loops (instant cycle).

Conclusion

Bellman-Ford and Floyd-Warshall together solve the entire family of shortest-path problems that Dijkstra cannot touch: any graph with negative edge weights, negative cycle detection, and all-pairs shortest paths.