# Question:Shortest path problem

## Question:Shortest path problem

Maple 16
`Modify the shortest path problem by rewriting a procedure Path, non-Recursion that print out the shortest path from a to e base on the information from  setShortestDistNode input:  destination "e" and setShortestDistNode output:  path : a -> b -> d -> e the total cost: 9hint: copy everything that we did in shortest path problem, and rewriting a procedure Path, with while loop `
`can someone help please? below is everything that we did in the shortest path problem. I'm sosrry that it's so long but if you can help it would be greatly appreciated!`
`>minCostNode := proc (setNode) local m, k, i; m := infinity; k := 0; for i to nops(setNode) do if setNode[i][3] < m then m := setNode[i][3]; k := i end if end do; return setNode[k] end proc`
`>NeighborEdge:=proc(nodeName::character,setEdge) local nEdges,i,setNeighbor;    nEdges:=nops(setEdge);  setNeighbor:={};   for i to nEdges do   if nodeName in setEdge[i] then      setNeighbor:={op(setNeighbor),setEdge[i]};   end if;  end do;  return setNeighbor;  end proc:`
`>RemoveElement:=proc(nodeName::character,setS)  local i,setTemp;      setTemp:=setS;    for i to nops(setS)  do   if nodeName in setS[i] then      setTemp:=setTemp minus {setS[i]};     end if;  end do;     return setTemp;    end proc:`
`>Relax:=proc(NodeU,setNeighborEdge,setNode)  local seqTmpNode,setTmpNode,tmpNode,eleNeighbor,NewnodeName,Newnodecost,i;  seqTmpNode:=NULL;  setTmpNode:=setNode;   for eleNeighbor in setNeighborEdge do if eleNeighbor[1] <> NodeU[1] then NewnodeName := eleNeighbor[1] else NewnodeName := eleNeighbor[2] end if    Newnodecost:=eleNeighbor[3];    for i to nops(setNode) do       tmpNode:=NULL;       if NewnodeName in setNode[i] then          if NodeU[3]+Newnodecost<setNode[i][3] then             tmpNode :=tmpNode,NewnodeName;             tmpNode := tmpNode,NodeU[1];             tmpNode:=tmpNode,NodeU[3]+Newnodecost;             seqTmpNode:=seqTmpNode,[tmpNode];             setTmpNode:=setTmpNode minus {setNode[i]};     end if;       end if;    end do;     end do;  return setTmpNode union {seqTmpNode};   end proc: `
`>ShortestDist := proc (setNode, setEdge) local setMinDistNode, setNeighborEdge, NodeU, setTmpNode, setTmpEdge; setMinDistNode := {}; setTmpNode := setNode; setTmpEdge := setEdge; while 0 < nops(setTmpNode) do NodeU := minCostNode(setTmpNode); setNeighborEdge := NeighborEdge(NodeU[1], setTmpEdge); setTmpEdge := RemoveElement(NodeU[1], setTmpEdge); setTmpNode := RemoveElement(NodeU[1], setTmpNode); setMinDistNode := `union`(setMinDistNode, {NodeU}); setTmpNode := Relax(NodeU, setNeighborEdge, setTmpNode) end do; return setMinDistNode end proc:`
`>setEdge := {["a", "b", 2], ["a", "c", 9], ["a", "g", 4], ["b", "c", 4], ["b", "d", 2], ["b", "f", 7], ["b", "g", 6], ["c", "d", 3], ["d", "e", 5], ["d", "f", 3], ["e", "f", 3], ["e", "h", 4], ["f", "g", 5], ["f", "h", 4], ["g", "i", 2], ["h", "i", 3]}`
`>setNode := {["a", "a", 0], ["b", 0, infinity], ["c", 0, infinity], ["d", 0, infinity], ["e", 0, infinity], ["f", 0, infinity], ["g", 0, infinity], ["h", 0, infinity], ["i", 0, infinity]}`
`>setShortestDistNode := ShortestDist(setNode, setEdge)`
`>Path := proc (NodeName::character, setS) local elementNode; if NodeName = "a" then return "a" else for elementNode in setS do if NodeName = elementNode[1] then return procname(elementNode[2], setS), elementNode[1] end if end do end if end proc`
`>seqPath := Path("e", setShortestDistNode)`
`>printPath := proc (destNode, setShortestDistNode) local totalcost, lstPath, nlenPath, strPath, i; for i to nops(setShortestDistNode) do if `in`(destNode, setShortestDistNode[i]) then totalcost := setShortestDistNode[i][3] end if end do; lstPath := [Path(destNode, setShortestDistNode)]; nlenPath := nops(lstPath); strPath := ""; for i to nlenPath do if i = nlenPath then strPath := cat(strPath, lstPath[i], " the total cost : ", totalcost) else strPath := cat(strPath, lstPath[i], "->") end if end do; printf("The shortest path is %s", strPath) end proc:`
`> printPath("e", setShortestDistNode);The shortest path is a->b->d->e the total cost : 9`
﻿