【図論】最短および最小生成ツリー
13259 ワード
【図論】最短および最小生成ツリー
2つのアルゴリズムはかなり類似性があり、貪欲な考えを使っているので、一緒に置いてください.最短回路でよく用いられるアルゴリズムはdijkstra,bellman−ford,floydである.最小生成ツリーはprimとkruskalです.以下に、各アルゴリズムのテンプレートを示します.Dijkstra:
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
対応する最小生成ツリーのprimテンプレート:
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
以下は最短のbellmen-fordアルゴリズムで、dijkstraとは異なり、bellman-fordは負の重み値を持つ図に適用できるが、複雑度が高く、O(VE)...慎重に~(SPFAは使えますが、そのアルゴリズムは私がよく身につけていません:D)
Bellman−fordアルゴリズムは,同様に各エッジに対してN−1回の緩和を行い,重み値が負の場合,すべてのエッジに対してN−1回の緩和を行い,disが更新されれば負のループがあることを示す.
Bellman-fordテンプレート:
アルゴリズムが終了するとdist配列はすでに最短経路となる.
2つのアルゴリズムはかなり類似性があり、貪欲な考えを使っているので、一緒に置いてください.最短回路でよく用いられるアルゴリズムはdijkstra,bellman−ford,floydである.最小生成ツリーはprimとkruskalです.以下に、各アルゴリズムのテンプレートを示します.Dijkstra:
1 #include<stdio.h>
2 #include<string.h>
3 #define INF 0x1f1f1f1f
4 #define M 1001
5 int map[M][M],dis[M];
6 bool flag[M];
7 void dijkstra(int s,int n,int t) //s ,n ,t
8 {
9 int i,j,k,md,temp;
10 for(i=1;i<=n;i++)
11 dis[i]=INF; // dis , 0
12 dis[s]=0;
13 memset(flag,false,sizeof(flag)); // flag false,
14 for(i=1;i<n;i++){ // n-1 ,
15 md=INF;
16 for(j=1;j<=n;j++){
17 if(!flag[j]&&dis[j]<md){
18 md=dis[j];
19 temp=j;
20 }
21 }
22 if(temp==t) break; // ,
23 flag[temp]=true; //
24 for(j=1;j<=n;j++){
25 if(!flag[j]&&md+map[temp][j]<dis[j]) //
26 dis[j]=md+map[temp][j];
27 }
28 }
29 }
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
対応する最小生成ツリーのprimテンプレート:
1 #include<iostream>
2 #define INF 0x1f1f1f1f
3 #define M 1000
4 using namespace std;
5 double dis[M],map[M][M];
6 bool flag[M];
7 int prim(int s,int n) //s ,n
8 {
9 int i,j,k,temp,md,total=0;
10 for(i=1;i<=n;i++)
11 dis[i]=map[s][i]; // , dis map[s][i]
12 memset(flag,false,sizeof(flag));
13 flag[s]=true; //
14 for(i=1;i<n;i++){ // n-1 ,
15 md=INF;
16 for(j=1;j<=n;j++){
17 if(!flag[j]&&dis[j]<md){
18 md=dis[j];
19 temp=j;
20 }
21 }
22 flag[temp]=true; //
23 total+=md; // total
24 for(j=1;j<=n;j++) // ,
25 if(!flag[j]&&dis[j]>map[temp][j])
26 dis[j]=map[temp][j];
27 }
28 return total;
29 }
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
以下は最短のbellmen-fordアルゴリズムで、dijkstraとは異なり、bellman-fordは負の重み値を持つ図に適用できるが、複雑度が高く、O(VE)...慎重に~(SPFAは使えますが、そのアルゴリズムは私がよく身につけていません:D)
Bellman−fordアルゴリズムは,同様に各エッジに対してN−1回の緩和を行い,重み値が負の場合,すべてのエッジに対してN−1回の緩和を行い,disが更新されれば負のループがあることを示す.
Bellman-fordテンプレート:
1 #include<stdio.h>
2 #include<string.h>
3 #define INF 0x1f1f1f1f
4 #define MAX 102
5 #define MAXM 20008
6
7 int dist[MAX];
8
9 struct Edge{ //
10 int u, v, w;
11 Edge(){}
12 Edge(int a, int b, int c):u(a), v(b), w(c){}
13 }edge[MAXM];
14
15 int bellman_ford(int n, int m, int s) //n 、m 、s
16 {
17 memset(dist, 0x1f, sizeof(dist)); //
18 dist[s] = 0;
19 int i, j, u, v, f;
20 for (i = 1; i < n; ++i) // n - 1 , n-1
21 {
22 f = 0;
23 for (j = 0; j < m; ++j)
24 {
25 u = edge[j].u;
26 v = edge[j].v;
27 if (dist[v] > dist[u] + edge[j].w) //
28 {
29 dist[v] = dist[u] + edge[j].w;
30 f = 1;
31 }
32 }
33 if (!f) return 1; // ,
34 }
35 for(j = 0; j < m; ++j) //
36 {
37 u = edge[j].u;
38 v = edge[j].v;
39 if (dist[v] > dist[u] + edge[j].w) // ,
40 return -1; // -1
41 }
42 return 1; // 1
43 }
アルゴリズムが終了するとdist配列はすでに最短経路となる.