Write an Octave (or another language/package) function that takes as input the f

Question

Write an Octave (or another language/package) function that takes as input the forward star representation of a network and a starting node s, And finds the shortest path to all nodes using Dijkstra's algorithm. The program should output the pred vector as well as the shortest path length (the vector d). Write an Octave (or another language/package) function that takes as input the forward star representation of a network and a starting node s, And finds the shortest path to all nodes using Dijkstra's algorithm. The program should output the pred vector as well as the shortest path length (the vector d). And finds the shortest path to all nodes using Dijkstra's algorithm. The program should output the pred vector as well as the shortest path length (the vector d).

Explanation / Answer

The algorithm takes as input a string containing a network definition.

The assumption is made that nodes are numberd 1:N, where N is the number

of nodes.

A network definition is a list containing sublists with numeric sequences; which
define the network.

1. The first sublist contains the number of nodes in the network,
   the number of arcs and the source node s.

   For example: [4, 7, 5] defines a network with 4 nodes and 7 arcs
   and says that node 5 is the source node to find shortest paths from.

2. The remaining sublists define the arcs in the network. Each

   specifies the start node, end node and cost of traveling the arc.

   For example: '2 5 15' defines an arc from 2 to 5 with cost 15.

Example network definion (4 nodes, 6 arcs, source node is 1):

net := [

[4, 6, 1],

[1, 2, 1],

[1, 3, 3],

[2, 3, 2],

[3, 2, 4],

[2, 4, 5],

[3, 4, 9]

];

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.