0
$\begingroup$

I am attempting to write a module that prints an optimal path from a starting node to a destination node. The first node is 1 and the final node is 100 (though when module prints these they should be 0 and 99 respectively). The module takes as inputs a distance matrix, Q, and a list, J, whose elements are the shortest-path weight from node i to destination node. Below is my best attempt.

findPathandTotalCost3[Q_, J_] := Module[
  {costs, node, v, w, i},
  i = 1;
  costs[i_] := 
   costs[i] = Table[Q[[node[i], w]] + J[[w]], {w, Length[J]}];
  node[1] = 1;
  node[2] = Position[costs[1], Min[costs[1]]];
  node[i] = Position[costs[i - 1], Min[costs[i - 1]];
    While[node[i] < 100,
     (Print[node[i] - 1]; ++i; costs[i]; node[i];)];];]

All my attempts at implementing this module seem to have problems with either correctly iterating or specifying which parts are recursive. Below is a typical error output.

findPathandTotalCost3[Q, J]

Part::pkspec1: The expression node$45807[0] cannot be used as a part specification.

Part::pkspec1: The expression node$45807[0] cannot be used as a part specification.

Part::pkspec1: The expression node$45807[0] cannot be used as a part specification.

General::stop: Further output of Part::pkspec1 will be suppressed during this calculation.

0

As can be seen, the first node prints correctly ("0") but the module subsequently doesn't evaluate properly.

Does anyone have any suggestions as to how to make this work? I can post more of my code attempts if helpful. Thanks

EDIT: Q and J below. Q is too large to paste in full, but is a list of 100 lists, each similar to:

{Infinity, 0.04, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, 11.11, Infinity, Infinity, Infinity, Infinity, Infinity, 72.21, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, 
  Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, 
  Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, 
  Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, 
  Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity}, 
 {Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, 20.59, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, 64.94, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, 
  Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, 
  Infinity, Infinity, Infinity, Infinity, 1247.25, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, 
  Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, 
  Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity}

where, e.g. 0.04 is the edgeweight 1->2.

J:

{160.55, 162.26, 88.52, 143.73, 145.12, 147.43, 141.67, 144.1, \
149.44, 140.95, 150.8, 141.99, 148.93, 303.77, 130.85, 107.01, \
128.15, 114.66, 104.44, 124.66, 124.42, 168.62, 200.27, 88.21, \
114.61, 102.74, 112.81, 112.8, 131.97, 70.38, 71.45, 176.51, 66.16, \
65.84, 110.18, 64.7, 156.07, 67.8, 67.44, 63.95, 77.15, 62.61, 58.66, \
149.25, 50.72, 52.26, 67.53, 48.58, 65.21, 46.27, 45.76, 54.36, \
135.03, 44.38, 54.99, 42.16, 40.05, 40.03, 62.47, 30.69, 33.02, 37.5, \
35.56, 38.77, 32.62, 34.98, 34.34, 31.39, 31.68, 30.47, 30.41, 30.02, \
35.96, 22.04, 21.16, 21.45, 20.64, 42.31, 79.71, 8.91, 33.37, 77.12, \
15.27, 10.37, 33.5, 7.46, 85.72, 4.8, 4.59, 37.6, 13.56, 22.8, 11.87, \
3.28, 3.09, 0.27, 1.06, 0.63, 0.33, 0}
$\endgroup$
12
  • $\begingroup$ Hi, on my machine with V13 I have not been able to reproduce your errors. I am attaching a screenshot so you can check for yourself $\endgroup$
    – bmf
    Mar 22 at 6:31
  • $\begingroup$ How do you expect someone to run your code if they do not have access to Q and J ? But see partpkspec1-the-expression-j-cannot-be-used-as-a-part-specification $\endgroup$
    – Nasser
    Mar 22 at 6:33
  • 1
    $\begingroup$ @bmf you need Q and J to run the code. $\endgroup$
    – Nasser
    Mar 22 at 6:34
  • $\begingroup$ Hi @Nasser I have added J and (some of) Q $\endgroup$
    – J0ta
    Mar 22 at 6:44
  • $\begingroup$ You could make a Minimal input? The error you see is not related to how large J and Q are. And it is better to paste the input using InputForm to make it easier to copy. $\endgroup$
    – Nasser
    Mar 22 at 6:47

1 Answer 1

0
$\begingroup$

For explicitness, I'll generate some fake data and then use the built-in functions.

weightedAdjacencyMatrix =
  With[
    {maxWeightCount = 15, nodeCount = 10, maxWeight = 20},
    With[
      {edgeCoordinates = 
        DeleteCases[
          RandomInteger[{1, nodeCount}, {maxWeightCount, 2}], {a_, a_}]},
      SparseArray[
        MapThread[
          Rule, 
          {edgeCoordinates, 
           RandomReal[{0, maxWeight}, 
             Length@edgeCoordinates]}], 
        {nodeCount, nodeCount}, 
        Infinity]]]

We can create a Graph directly from this.

graph = 
  WeightedAdjacencyGraph[weightedAdjacencyMatrix, 
    VertexLabels -> "Name", EdgeLabels -> "EdgeWeight"]

The options aren't necessary, but can be useful later to understand verify the results.

The following will give you the shortest path (using the edge weights).

FindShortestPath[graph, 1, 10]

And the next will give you the distance.

GraphDistance[graph, 1, 10]

Does that answer your question? Obviously I chose a small graph for clarity/experimentation, but could this be applied to your situation? I've left out how to mulitply the path weightings (contained in J) to the edge weightings (contained in Q).

$\endgroup$
4
  • $\begingroup$ thanks for your answer. Sorry I forgot to mention in my last response to you that this is a school assignment and therefore I have to build a FindShortestPath module myself. I'll paste the instruction below. "Write a module findPathAndTotalCost that takes a distance matrix, Q and a cost-to-go function J and uses them to find the optimal (cheapest) path from start to end and its cost. Test your code on the data in the graph.txt file by showing the optimal path and finding its minimum cost. Hint: Your findPathAndTotalCost should of course make use of the findCostToGo module". $\endgroup$
    – J0ta
    Mar 22 at 22:41
  • $\begingroup$ Oh! Sorry! Looking back I should have realized this. $\endgroup$
    – lericr
    Mar 22 at 23:13
  • $\begingroup$ Are you required to use an imperative/While-loop approach? I would have started thinking about NestWhile or FixedPoint. $\endgroup$
    – lericr
    Mar 22 at 23:39
  • $\begingroup$ no, the only requirement is that it's in a module and calls Q, J, and uses the cost-to-go module which I have already written. What I included in the previous comment is all the requirements stipulated $\endgroup$
    – J0ta
    Mar 23 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.