【図論】最短および最小生成ツリー

13259 ワード

【図論】最短および最小生成ツリー
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, 0x1fsizeof(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配列はすでに最短経路となる.