# PeopleSoft to AI | Part 16: Uniform-Cost Search — What If Every Action Has a Different Cost? > Source: > Published: 2026-08-25 06:00:20+00:00 In the [ previous article](https://medium.com/@gokulkalauni03/peoplesoft-to-ai-part-15a-depth-first-search-dfs-explained-simply-d092a8ad85ac?sharedUserId=gokulkalauni03), we looked at DFS is useful when we want to find a path through a search space. But what if finding *any* path isn’t enough? What if every action has a different cost? Maybe one action takes one second while another takes ten. Maybe one route uses fewer resources, while another requires more computation. In that situation, the shortest path isn’t necessarily the best path. We need a search algorithm that considers **cost**. That is where **Uniform-Cost Search (UCS)** comes in. **A Small Change in Perspective** Up to this point, we’ve used PeopleSoft examples to make the concepts familiar. From here, we’ll sometimes use simpler, generic examples when they explain the algorithm more clearly. The goal isn’t to force every algorithm into a PeopleSoft scenario. It’s to understand the algorithm well enough to recognize where it can eventually be useful in enterprise systems and AI. For UCS, a weighted graph gives us a much better way to understand the idea. **The Problem** Imagine we have a graph where every connection has a different cost. Our goal is simple: Find the cheapest path from START to TREASURE. Here’s the graph we’ll use throughout this article: The graph contains several possible routes to TREASURE. The edge costs are: ``` START → A Cost 2START → B Cost 1A → C Cost 2A → D Cost 1B → E Cost 4B → F Cost 1C → G Cost 3D → G Cost 1D → H Cost 2E → H Cost 1F → I Cost 2G → TREASURE Cost 2H → TREASURE Cost 1I → TREASURE Cost 4 ``` There are multiple ways to reach the same destination. For example: ``` Route ASTART → A → C → G → TREASURECost = 2 + 2 + 3 + 2 = 9 ``` Another route is: ``` Route BSTART → A → D → G → TREASURECost = 2 + 1 + 1 + 2 = 6 ``` We also have: ``` Route CSTART → B → E → H → TREASURECost = 1 + 4 + 1 + 1 = 7 ``` And: ``` Route DSTART → B → F → I → TREASURECost = 1 + 1 + 2 + 4 = 8 ``` All four routes reach the same destination. But they don’t have the same total cost. The cheapest route is: ``` START → A → D → G → TREASURETotal Cost = 6 ``` The question is: How can an algorithm discover that route without simply trying every complete route first? That’s where Uniform-Cost Search comes in. **From Depth to Cost** DFS primarily cares about going deeper. BFS primarily cares about the number of steps. UCS cares about the **total cost accumulated so far**. That’s the fundamental difference. Imagine we start at START. There are two immediate choices: ``` START → A Cost = 2START → B Cost = 1 ``` A normal FIFO queue would process nodes according to discovery order. UCS doesn’t. It places both paths into a priority queue and chooses the one with the lowest accumulated cost: ``` Priority QueueSTART → B Cost = 1START → A Cost = 2 ``` So B is expanded first. This is important because a node that is discovered later can still be explored before a node that was discovered earlier if its path is cheaper. That’s the fundamental idea behind UCS. **Cumulative Cost** The important detail is that UCS doesn’t look only at the cost of the next edge. It tracks the total cost from START to the current node. We usually represent this as: ``` g(n) ``` where g(n) means: The cost of the path from the starting node to node n. For example: ``` START | | 1 ↓ B | | 1 ↓ F | | 2 ↓ I ``` Therefore: ``` g(B) = 1g(F) = 1 + 1 = 2g(I) = 1 + 1 + 2 = 4 ``` The edge leading to I costs 2. But the cost of the path reaching I is 4. That distinction is critical. UCS works with **accumulated path cost**, not isolated edge cost. **How UCS Actually Works** Let’s walk through the exact graph step by step. Initially: ``` Priority QueueSTARTCost = 0 ``` We pop START. It has two possible next states: ``` START → A Cost = 2START → B Cost = 1 ``` So the priority queue becomes: ``` Priority QueueSTART → B Cost = 1START → A Cost = 2 ``` UCS chooses START → B because its accumulated cost is lower. From B, there are two possible next states: ``` START → B → E Cost = 1 + 4 = 5START → B → F Cost = 1 + 1 = 2 ``` The queue now contains: ``` Priority QueueSTART → A Cost = 2START → B → F Cost = 2START → B → E Cost = 5 ``` There is now a tie at cost 2. The important thing is that UCS only cares about the **priority value** here: the accumulated cost. Our implementation can use a secondary ordering to decide which equal-cost entry is processed first. In the execution shown in the companion video, A is processed before F. From A, we can reach C and D: ``` START → A → C Cost = 2 + 2 = 4START → A → D Cost = 2 + 1 = 3 ``` The queue now contains: ``` Priority QueueSTART → B → F Cost = 2START → A → D Cost = 3START → A → C Cost = 4START → B → E Cost = 5 ``` UCS chooses START → B → F next because 2 is the lowest cost. From F, we reach I: ``` START → B → F → ICost = 1 + 1 + 2 = 4 ``` The queue now contains: ``` Priority QueueSTART → A → D Cost = 3START → A → C Cost = 4START → B → F → I Cost = 4START → B → E Cost = 5 ``` UCS chooses START → A → D because its accumulated cost is 3. From D, there are two possible next states: ``` START → A → D → GCost = 2 + 1 + 1 = 4 ``` and: ``` START → A → D → HCost = 2 + 1 + 2 = 5 ``` The queue now contains several candidates: ``` Priority QueueSTART → A → C Cost = 4START → B → F → I Cost = 4START → A → D → G Cost = 4START → B → E Cost = 5START → A → D → H Cost = 5 ``` Notice what UCS is doing. It isn’t following one complete route from beginning to end. It is continuously comparing the **cheapest available partial paths**. That is what makes UCS different from DFS. Now suppose the path through C is expanded: ``` START → A → C → GCost = 2 + 2 + 3 = 7 ``` But we already have a cheaper way to reach G: ``` START → A → D → GCost = 4 ``` So the path through C isn’t competitive. This is another important property of UCS: reaching the same node through different paths doesn’t automatically mean all paths are equally useful. The accumulated cost matters. Eventually, UCS expands: ``` START → A → D → G ``` with: ``` Cost = 4 ``` From G, we can finally reach TREASURE: ``` START → A → D → G → TREASURECost = 2 + 1 + 1 + 2 = 6 ``` The priority queue may still contain other paths. For example: ``` START → B → ECost = 5START → A → D → HCost = 5START → B → F → ICost = 4 ``` But the newly generated path to TREASURE has cost 6. Once TREASURE is popped from the priority queue, UCS can stop because, with non-negative edge costs, no later path can have a lower total cost. The final answer is: ``` START → A → D → G → TREASURETotal Cost = 6 ``` This is exactly the behaviour shown in the companion video. The important idea is: **UCS always expands the currently cheapest path, not simply the next path discovered.** **Watch UCS in Action** The graph is much easier to understand when you can actually watch the priority queue change after every step. The companion video for this article walks through the same graph and shows UCS selecting nodes based on their accumulated cost until it reaches TREASURE. As you watch it, pay attention to three things: ``` 1. Which node is selected next?2. What is its accumulated cost?3. Why is every other frontier entry more expensive? ``` Those three questions are essentially the UCS algorithm. **Why DFS Could Make a Different Choice** This is where UCS differs from DFS. DFS might follow one branch deeply: ``` START ↓A ↓C ↓G ↓TREASURE ``` It has found a valid solution. But that solution costs: ``` 2 + 2 + 3 + 2 = 9 ``` DFS doesn’t naturally stop and ask: “Is there another route that costs less?” UCS does. It keeps the frontier ordered by accumulated cost. In our graph, UCS eventually discovers: ``` START → A → D → G → TREASURECost = 6 ``` So DFS can find a solution without necessarily finding the cheapest solution. UCS is specifically designed to find the least-cost solution when the edge costs are non-negative. **What About BFS?** BFS gives us another useful comparison. BFS explores the graph level by level. That means it generally finds a path with the fewest edges, not necessarily the lowest total cost. Consider these two routes: ``` Route BSTART → A → D → G → TREASURE4 actionsCost = 2 + 1 + 1 + 2 = 6Route DSTART → B → F → I → TREASURE4 actionsCost = 1 + 1 + 2 + 4 = 8 ``` Both routes contain four edges. BFS has no reason to prefer one based on cost. UCS does. It calculates: ``` Route B = 6Route D = 8 ``` and therefore prefers Route B. But we can make the distinction even clearer by looking at routes with different numbers of steps. ``` Route BSTART → A → D → G → TREASURE4 actionsCost = 6 ``` versus: ``` START → B → F → I → TREASURE4 actionsCost = 8 ``` The number of steps alone tells us nothing about the actual cost. This is the fundamental difference. BFS optimizes for step count. UCS optimizes for accumulated cost, and a longer path can still be the cheaper one. This gives us a useful summary: **Algorithm** **What it primarily cares about** DFS Go deeper BFS Fewest steps UCS Lowest total cost The distinction becomes important whenever different actions have different costs. **The Priority Queue** The data structure behind UCS is a **min-priority queue**. Conceptually, at one point in our search it might look like: ``` ┌────────────────────────────────────────────┐│ Path Cost │├────────────────────────────────────────────┤│ START → A → D 3 ││ START → A → C 4 ││ START → B → F → I 4 ││ START → B → E 5 ││ START → A → D → H 5 │└────────────────────────────────────────────┘ ``` The search always takes the lowest-cost entry. In Python, we can implement this using heapq: ``` python import heapqpriority_queue = []heapq.heappush(priority_queue, (0, "START"))while priority_queue: cost, node = heapq.heappop(priority_queue) print(node, cost) ``` The important part isn’t the Python syntax. It is the concept: ``` pop → cheapest path ``` Every time UCS has to decide what to explore next, it chooses the path with the smallest accumulated cost. One small Python detail is worth knowing here: tuples such as (cost, node) work fine when node values are directly comparable, such as strings. If two entries have the same cost, heapq falls through to comparing the second element. If those values are incomparable, such as dictionaries, custom objects without ordering, or mixed types, Python can raise a TypeError. A standard fix is to add a monotonically increasing tiebreaker: ``` (cost, counter, node) ``` **A Simple UCS Implementation** We can represent the graph in Python: ``` graph = { "START": [ ("A", 2), ("B", 1) ], "A": [ ("C", 2), ("D", 1) ], "B": [ ("E", 4), ("F", 1) ], "C": [ ("G", 3) ], "D": [ ("G", 1), ("H", 2) ], "E": [ ("H", 1) ], "F": [ ("I", 2) ], "G": [ ("TREASURE", 2) ], "H": [ ("TREASURE", 1) ], "I": [ ("TREASURE", 4) ], "TREASURE": []} ``` Now we can implement UCS: ``` python import heapqdef uniform_cost_search(graph, start, goal): queue = [(0, start)] visited = set() while queue: cost, node = heapq.heappop(queue) if node in visited: continue visited.add(node) if node == goal: return cost for next_node, edge_cost in graph[node]: if next_node not in visited: total_cost = cost + edge_cost heapq.heappush( queue, (total_cost, next_node) ) return None ``` The important line is: ``` total_cost = cost + edge_cost ``` The search carries the accumulated cost forward as it explores the graph. That’s the heart of Uniform-Cost Search. **Why Is ****visited Marked on POP?** There is a deliberate difference here from the DFS implementation we saw earlier. In the DFS/BFS examples, we used the familiar rule of marking a node as visited before pushing it into the frontier. With UCS, that would be unsafe. A node can be reached through multiple paths with different costs: ``` START → A → C Cost = 10START → B → C Cost = 6 ``` If we mark C visited when the first path pushes it into the queue, we could accidentally lock in the more expensive path. UCS instead waits until C is **popped from the priority queue**. Because the priority queue always removes the lowest-cost entry first, the first time a node is popped, we know we are processing its cheapest discovered path under the non-negative-cost assumption. So this is not an inconsistency with the DFS rule. It is a deliberate consequence of using a **cost-ordered frontier**. **UCS Complexity** There is a computational cost to this extra bookkeeping. With a binary heap priority queue, UCS has a typical time complexity of: ``` O((V + E) log V) ``` where V is the number of vertices and E is the number of edges. DFS and BFS can operate in: ``` O(V + E) ``` because their stack/queue operations are constant-time in the usual implementation. UCS is slower because every push and pop involves maintaining the heap ordering. This connects directly to the **visited-on-pop** behavior we just discussed. A node can be discovered through multiple paths, so UCS may push multiple candidate entries into the heap before one of them is finally popped and finalized. For space complexity: ``` Visited set = O(V)Heap entries = O(E) in the worst caseTotal = O(V + E) ``` So UCS gives us a stronger guarantee about cost, but that guarantee comes with additional computation and memory overhead. **One Important Limitation** UCS works under an important assumption: **action costs should not be negative**. Here’s why that matters. Imagine UCS has already popped and finalized a node at cost 10: ``` START | | 10 ↓ A ``` Later, suppose the search discovers another route: ``` START | | 8 ↓ B | | -2 ↓ A ``` That second route reaches A with: ``` 8 + (-2) = 6 ``` But UCS has already popped A at cost 10 and marked it visited. It won’t revisit A. So it keeps the wrong answer: ``` Finalized cost = 10Actual cheaper cost = 6 ``` This is exactly why negative edges break the usual UCS optimality guarantee. With non-negative costs, a cheaper path cannot suddenly appear later by adding a negative edge. If A has already been popped at cost 10, any later path reaching A must have accumulated at least 10 before taking its final non-negative edge. So the first popped path is safe to finalize. **Does UCS Guarantee the Best Solution?** Under the standard conditions, including non-negative action costs, UCS guarantees that when it removes a goal from the priority queue, it has found a **least-cost path** to that goal. That’s a powerful property. The algorithm isn’t simply saying: “I found a path to the goal.” It is saying: “Based on the cost model I was given, this is the cheapest path, and under the algorithm’s assumptions, it is optimal.” Of course, there is an important caveat. The result is only as good as the **cost model**. If we assign the wrong costs, UCS can faithfully find the wrong “best” solution. The search algorithm can optimize the numbers we give it. It cannot decide whether those numbers accurately represent the real world. That’s an important lesson when applying classical algorithms to real-world problems. **Connecting UCS Back to PeopleSoft** Now let’s bring the idea back to the world we know. A PeopleSoft process can also be represented as a graph. For example: ``` PeopleSoft State ↓Possible Operations ↓Different Costs ↓Search ↓Lowest-Cost Path ↓Desired Business State ``` A node could represent a system state. An edge could represent an operation. The edge weight could represent execution time, processing effort, system impact, risk, or another measurable cost. The important point is that UCS doesn’t need to understand PeopleSoft. It doesn’t need to know what a component, process, voucher, integration, or business rule means. It only needs: ``` Current statePossible next statesCost of each transitionGoal state ``` That is an important idea when moving from enterprise software toward AI. We don’t necessarily need to put AI inside the algorithm. We first need to understand how a problem can be represented mathematically. Once the problem is represented correctly, algorithms can operate on that representation. **Where UCS Fits in Our Journey** So far, we’ve moved through three different ways of thinking about search: ``` BFS↓"Find the solution using the fewest steps."DFS↓"Go deep and see where this path takes me."UCS↓"Find the solution with the lowest total cost." ``` And this progression is important. We’re gradually moving from **blind exploration** toward **more informed decision-making**. DFS doesn’t care about cost. BFS cares about the number of steps. UCS cares about the accumulated cost. But UCS still has a limitation. It has no idea whether it is moving **toward the goal**. Imagine our search space has thousands of possible states. UCS can correctly identify the cheapest paths so far, but it may spend a lot of time exploring cheap paths that ultimately lead nowhere useful. What if we could give the search a clue? What if it could estimate: “This state looks much closer to the goal than that one.” Now the search could become even more focused. And that leads us to the next step. **Coming Up Next** We’ve now introduced **cost-aware search**. But cost alone isn’t enough when the search space becomes large. Our search problem needs another piece of information: an estimate of **how promising a state is**. That idea of using an estimate to guide the search is called a **heuristic**. In the next article: **Part 17: Greedy Best-First Search — What If the AI Could Guess Which Path Looks Promising?** We’ll see what happens when we stop looking only at the cost we’ve already paid and start using an estimate of where we should go next. **About This Series** **PeopleSoft to AI** documents my transition from ERP development to AI engineering. Rather than treating AI and enterprise software as separate worlds, I’m exploring how the concepts I learn in AI connect with the systems I’ve spent nearly a decade building and supporting. The goal isn’t to present myself as an AI expert. It’s to document the learning process honestly, connect theory with real enterprise scenarios, and hopefully make the journey a little easier for other ERP professionals who are curious about AI but aren’t sure where to begin. [PeopleSoft to AI | Part 16: Uniform-Cost Search — What If Every Action Has a Different Cost?](https://pub.towardsai.net/peoplesoft-to-ai-part-16-uniform-cost-search-what-if-every-action-has-a-different-cost-29598bc6d2bc) was originally published in [Towards AI](https://pub.towardsai.net) on Medium, where people are continuing the conversation by highlighting and responding to this story.