Cyclomatic Complexity (complexity)
Cyclomatic complexity
is a measure of the number of possible paths thorough some code. For example an if statement with one clause eg if (foo) {} has two paths, One if foo is true and one if false. Any point where the code can branch, the branches are counted as part of the cyclomatic complexity.
Unfortunately how the complexity is summed differs so without knowing how the metric was calculated there is no easy way to give an answer. The best you can do is reduce the number of possible branches in the code.
Improving the code
Looking at your code and there is plenty of room to reduce the number of branches.
The function shortestCostNode is not needed as the shortest link in a node has no influence on the final result. The shortest link may well move you to the longest path. Searching for the shortest link is no improvement on picking nodes sequentially.
shortestCostNode is the major source of complexity in your solution, it effectively randomizes your search. Because of this you must track which path you have traveled so you don't end up repeating the same path, this adds a lot of baggage.
If you systematically search all possible paths in order (keeping track of where you have not been) you eliminate the need to track where you have been and can thus remove a lot of code.
Use a stack to search a tree
As the search for the shortest path involves traveling along paths and then backtracking to the nearest untraveled branch a stack is the best way to keep track of your progress.
You start at a node, push all paths and the cost so far to a stack, then pop one path and move along that path to the next node adding the cost as you do. Then do the same for the next node.
When you reach an end node you then check the distance and if it is the shortest so far you save that distance and the path traveled. Then pop the next path step from the stack until all paths have been checked.
A Recursive stack
The simplest (but not the quickest) way to implement a stack is via recursion.
Thus you end up with a function something like
function shortestPath(graph) {
    const result = {distance: Infinity}, endName = &quot;end&quot;;
    function followPath(node, totalDist = 0, path = [&quot;start&quot;]) {
        for (const [name, length] of Object.entries(node)) {
            const distance = totalDist + length;
            if (distance &lt; result.distance) {
                if (name === endName) {  
                    Object.assign(result, {distance, path: [...path, endName]}); 
                } else {
                    path.push(name);
                    followPath(graph[name], distance, path);
                    path.pop();
                }
            }
        }
    }
    followPath(graph.start);
    return result;
}

The function has a Cyclomatic complexity of about 5.
Note that the function only follows paths while the distance traveled is less than the shortest path found already found. This means that you may not need to check all paths to the end.
There is also plenty of room for improvement (in terms of complexity and performance), but as you have not defined much about the graphs possible structure there is no point going any further,.