algorithm - Find a minimum weight spanning tree in the undirected graph where there are negative edges -

so need solve graph, have general idea on how solve if doing wrong please correct me.

so find mst need perform kruskals algorithm on graph

here psuedocode kruskals algorithm

kruskal(v,e) = null; each v contains in v make disjoint set(v) sort e weight increasingly each(v1, v2) contains in e if

  kruskal(v,e)
  
a = null; each v contains in v      make disjoint set(v) sort e weight increasingly each(v1, v2) contains in e       if find(v1) not equal find(v2)           = union {(v1,v2)}           union(v1,v2) return a

so first thing find nodes shortest distances right?

1)

i assume s h has shortest distance since d(h,s) = -3

so = {(h,s)}

so follow pattern

2) = {(h,s),(s,f)}

3) = {(h,s),(s,f)(s,n)}

4) = {(h,s)(s,f)(s,n)(f,k)}

5) = {(h,s)(s,f)(s,n)(f,k)(s,m)} (we skip h n because path made h n through s )

6) = {(h,s)(s,f)(s,n)(f,k)(s,m)(d,b)}

7) = {(h,s)(s,f)(s,n)(f,k)(s,m)(d,b)(b,m)}

so since there path connects edges right?

but thing dont understand there there distance[u,v] shorter path[u,v] through multiple vertices. example d[d,m] shorter p[d,m] goes through b first. doing wrong?

you're not doing wrong. there's no guarantee mst preserves shortest distances between nodes. eg: 3 node complete graph abc edge weights 3, 2, 2 (with apologies ascii art):

a --- 2 --- b |           | 2          / |         / c----3---/  

the minimal spanning tree c-a-b distance between b , c in original graph 3, , in mst 4.