Task 2 — Weighted Route Resolution

Objective

Create a function that finds the lowest-cost route between two nodes in a weighted graph.

The function must return:

• the selected path
• the total route cost

The graph represents bidirectional connections.

Node Model

Each location is identified by a string ID.

Example:

A
B
C
D
E
F

Edge Model

Each connection contains:

From
To
Cost

A possible model is:

type Edge struct {
    From string
    To   string
    Cost int
}

Input Graph

Use the following connections:

edges := []Edge{
    {From: "A", To: "B", Cost: 4},
    {From: "A", To: "C", Cost: 2},
    {From: "B", To: "C", Cost: 1},
    {From: "B", To: "D", Cost: 5},
    {From: "C", To: "D", Cost: 8},
    {From: "C", To: "E", Cost: 10},
    {From: "D", To: "E", Cost: 2},
    {From: "D", To: "F", Cost: 6},
    {From: "E", To: "F", Cost: 3},
}

All edges are bidirectional.

Therefore:

A -> B

also allows:

B -> A

with the same cost.

Function

Conceptually:

FindLowestCostRoute(
    edges,
    source,
    target,
)

Example Request

Find the lowest-cost route from:

A

to:

F

Candidate Routes

One possible route is:

A -> C -> E -> F

Cost:

2 + 10 + 3 = 15

Another route is:

A -> B -> D -> F

Cost:

4 + 5 + 6 = 15

Another route is:

A -> C -> B -> D -> E -> F

Cost:

2 + 1 + 5 + 2 + 3 = 13

Therefore the lowest-cost route is:

A -> C -> B -> D -> E -> F

with total cost:

13

Expected Result

A possible result model is:

type RouteResult struct {
    Found bool
    Path  []string
    Cost  int
}

Expected result:

RouteResult{
    Found: true,
    Path: []string{
        "A",
        "C",
        "B",
        "D",
        "E",
        "F",
    },
    Cost: 13,
}

No Route

If the target cannot be reached from the source:

RouteResult{
    Found: false,
}

should be returned.

Do not return an arbitrary partially completed path.

Source Equals Target

For:

source = A
target = A

the route is valid immediately.

Expected result:

RouteResult{
    Found: true,
    Path:  []string{"A"},
    Cost:  0,
}

Cost Validation

Route costs must not be negative.

This task assumes:

cost >= 0

for every edge.

Negative costs should be rejected as invalid input.

Missing Node

If either:

source

or:

target

does not exist in the graph, return a validation error.

Duplicate Connections

If multiple edges connect the same two nodes, the implementation must define how they are handled.

One reasonable rule is to preserve all valid edges and allow the route algorithm to naturally choose the cheapest one.

Equal-Cost Routes

Multiple routes may have the same total cost.

When several routes have equal minimum cost, use a deterministic tie-breaking rule.

One possible rule is:

select the lexicographically smallest complete path

The implementation must document the chosen rule.

Requirements

The function must:

1. validate the graph
2. verify that source and target exist
3. find the lowest total route cost
4. reconstruct the complete selected path
5. return the path and total cost
6. report when no route exists
7. avoid infinite traversal through cycles

Additional Test

Find the lowest-cost route from:

A

to:

D

Possible routes include:

A -> B -> D
cost = 9

and:

A -> C -> B -> D
cost = 8

Therefore the expected lowest cost is:

8

with path:

A -> C -> B -> D

Implementation Notes

This is a weighted shortest-path problem.

An efficient implementation should avoid enumerating every possible route when unnecessary.

The algorithm should work with arbitrary graph sizes and must not depend on the supplied node names.