Recap Graph Day 2

Weighted Shortest Path

• Dijkstra’s Algorithm (implementation)

if(dist[n] + x.second < dist[x.first]){
	dist[x.first] = dist[n] + x.second;
}

• Bellman-Ford
  • Negative cycles
• Floyd-Warshall (implementation)

for(int k = 0; k < N; k++){
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			if(dist[i][k] == INT_MAX || dist[k][j] == INT_MAX) continue;
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
		}
	}
}

• Johnson (exist)
• A* Search

Minimum Spanning Tree

• Kruskal’s (implementation)

  • Union-find

    sort(v.begin(), v.end());
    
    int ans = 0;
    for(auto x : v){
    	int hx = findpa(x.second.first), hy = findpa(x.second.second);
    	if(hx != hy){
    		ans += x.first;
    		pa[hx] = hy;
    	}
    }

• Prim’s

Proof

https://cp-algorithms.com/graph/dijkstra.html

https://wcipeg.com/wiki/Floyd–Warshall_algorithm

https://cp-algorithms.com/graph/mst_kruskal.html