6.4.27 Graph theory

Problem: A weighted graph is defined by a matrix of arc lengths. Plot the graph. Find: a) the spanning tree of minimum weight; b) the shortest distance from vertex \( v_{4} \) to the remaining vertices of the graph, using Dijkstra's algorithm. \[ \left[\begin{array}{cccccc} \infty & \infty & \infty & 2 & 3 & 4 \\ \infty & \infty & 3 & \infty & 1 & 2 \\ \infty & 3 & \infty & 5 & \infty & 1 \\ 2 & \infty & 5 & \infty & 4 & 1 \\ 3 & 1 & \infty & 4 & \infty & \infty \\ 4 & 2 & 1 & 1 & \infty & \infty \end{array}\right] \]