So, I have to find the minimal spanning tree in the graph in the picture. Below are my results. I feel like I shouldn't get 2 different weights, but I can't find a mistake.
Can Kruskal’s and Prim’s algorithm give trees with different weight
discrete optimizationgraph theorytrees
Best Answer
You didn’t carry out Prim’s algorithm correctly. I’m assuming that you started with $v_1$, added the edge to $v_2$, and then added the edge from $v_2$ to $v_3$. That much is fine, but then you added the edge from $v_3$ to $v_5$, when you should have added the edge from $v_2$ to $v_5$: of all of the edges between the partial tree that you’d constructed up to that point and the other vertices of the graph, the one between $v_2$ and $v_5$ has the lowest weight. Specifically, the edges available for adding at that point, with their weights, are as follows, with the edge of lowest weight shown in red:
$$\begin{array}{c|cc} \text{Edge}&\text{Weight}\\\hline v_1v_4&11\\ v_1v_5&9\\ v_2v_4&9\\ \color{red}{v_2v_5}&\color{red}8\\ v_3v_5&10 \end{array}$$
At each stage you should add the edge of lowest weight between any vertex of the partial tree that you’ve constructed up to that point and any vertex not in that partial tree.