Optimisation problems differ from decision problems in that they seek the best solution from a range of possibilities, whereas decision problems are concerned with yes-or-no answers. In an optimisation problem, the aim is to maximise or minimise a measurable value—such as cost, distance, or time—while meeting certain constraints. For example, in route planning, the optimisation problem would ask, “What is the shortest route from A to B?” In contrast, a decision problem would ask, “Is there a route from A to B that is shorter than 50km?” Optimisation problems are typically more complex because they require evaluating multiple potential solutions and comparing them to find the optimal one. They often use objective functions and constraints to determine the most effective answer, while decision problems focus on evaluating a single condition. Furthermore, many optimisation problems can be transformed into decision problems and vice versa, depending on the context and computational goal.

Non-negative edge weights are essential in many shortest path algorithms—such as Dijkstra’s algorithm—because these algorithms rely on the assumption that adding an edge to a path cannot make the total cost lower. This assumption allows the algorithm to make reliable decisions as it proceeds, marking nodes as having the shortest possible path once visited. If negative edge weights are present, this guarantee breaks down, and a previously determined shortest path could later turn out to be suboptimal if a negative-weight edge is found. In such cases, algorithms like Dijkstra’s may produce incorrect results or fail entirely. For graphs with negative weights, alternative algorithms like Bellman-Ford must be used, as they are designed to handle cases where costs can decrease along a path. The presence of negative cycles—where repeatedly looping through a cycle reduces the total cost—can even make shortest path problems unsolvable unless detected and managed properly.

Modelling optimisation problems with graphs in the real world involves several challenges. Firstly, accurately representing entities and relationships can be complex. For example, in a road network, roads can change direction, support varying speed limits, or experience closures, making it difficult to model edges consistently. Secondly, data may be incomplete, outdated, or dynamic. In logistics, traffic conditions, delivery times, or fuel prices may change frequently, which affects edge weights in real time. This requires adaptive models or algorithms that can update efficiently. Thirdly, scaling graphs for large networks (like international transport systems or the internet) introduces performance issues, as computational resources must process millions of nodes and edges. Lastly, real-world constraints—such as road restrictions, time windows, or resource limits—are often complex and difficult to represent as simple edge weights, requiring additional modelling layers or hybrid algorithms. Balancing accuracy and computational efficiency remains a key challenge in graph-based optimisation.

The presence of multiple shortest paths—where two or more routes between the same nodes have equal total weights—affects optimisation algorithms in several ways. While most shortest path algorithms, such as Dijkstra’s, are designed to find a shortest path, they do not necessarily return all possible shortest paths. This can be problematic in applications like load balancing or redundancy planning, where identifying all optimal options is important. Algorithms may need to be adapted or extended to track multiple equally short paths, requiring additional data structures and more computational time. Additionally, the choice among equal-length paths can influence downstream decisions. For instance, in a navigation system, different shortest paths might pass through different toll roads or scenic routes, affecting user satisfaction. Some systems use secondary criteria (e.g. traffic, user preference) to rank among equally optimal paths. Therefore, recognising and handling multiple shortest paths is crucial in ensuring robust and user-centred optimisation.

Not all optimisation problems can be solved efficiently by computers. Some problems are computationally simple and can be solved in polynomial time using algorithms like Dijkstra’s or Prim’s. However, many real-world optimisation problems belong to the class of NP-hard or NP-complete problems, meaning that no known algorithm can solve them efficiently (in polynomial time) as the problem size grows. Examples include the Travelling Salesman Problem and vehicle routing with time windows. In such cases, exact solutions may be computationally infeasible for large instances, and computers must resort to heuristic or approximation algorithms that provide good enough solutions within practical time limits. Even for problems that are solvable in theory, practical constraints—like limited memory, real-time requirements, or dynamic data—can prevent efficient computation. As a result, optimisation often involves trade-offs between speed, accuracy, and resource usage, especially in complex or time-sensitive systems such as live traffic management or financial trading platforms.