図論-最短経路2.DijkstraアルゴリズムO(N 2)

2.
Dijkstra
アルゴリズム#アルゴリズム#
O (N
2
)
計算に使用
1つのポイントから他のすべてのポイントへの最短パスのアルゴリズム
ああ、一種の
単一ソース最短パスアルゴリズム
.つまり、
始点が一つしかない場合のみ
.
D
ijkstraの時間的複雑さは
O (N
2
)
ああ、それは
負のエッジ権がある場合は処理できません
.
アルゴリズムの説明:
      
始点を
s
,
dis[v]
から
s
に着く
v
の最短経路で、
pre[v]
を選択します.
v
の前駆ノードで、パスを出力します.
      
a)初期化:
dis[v]=
∞
(v
≠
s); dis[s]=0; pre[s]=
0
;
      
b)
For
(i = 1; i <= n ; i++)
            1.
アクセスされていないポイントで頂点を探します
u
にさせる
dis[u]
一番小さいです.
            2.u
最短パスとしてマーク
            3.For
と
u
接続されている各最短パスの頂点
v
              if
 (
dis[u]+w[u
][
v]
<
dis[v]
)
              
{
                  dis[v]
=
dis[u]
+
w[u
][
v];
                  pre[v]
=
u;
              
}
       
c)アルゴリズム終了:
dis[v]
を選択します.
s
に着く
v
の最短距離;
pre[v]
を選択します.
v
の前駆ノードで、パスを出力します.

 1 #include
 2 #include
 3 #define N 1010
 4 #define MAXX 9999999
 5 int dis[N];
 6 int map[N][N];
 7 int qq[N];
 8 int que[N];
 9 int n,m,bein,s,ss;
10 int visit[N];
11 void work(int s)
12 {
13     visit[s]=1;
14     for(int k=1;k<=n;++k)
15     {
16         dis[k]=map[s][k];
17         if(map[s][k]!=MAXX)qq[k]=s;
18         else qq[k]=0;
19     }
20     visit[s]=1;
21     dis[s]=0;
22     for(int I=1;II)
23     {
24         int k=s,minn=MAXX;
25         for(int j=1;j<=n;++j)
26         {        
27             if(!visit[j]&&dis[j]<minn)
28             {
29                 minn=dis[j];
30                 k=j;
31             }
32         }
33         visit[k]=1;
34         for(int i=1;i<=n;++i)
35         {
36             if(map[k][i]&&!visit[i]&&dis[i]>dis[k]+map[k][i])
37             {
38                 dis[i]=dis[k]+map[k][i];
39                 qq[i]=k;
40             }
41         }
42     }
43     printf("%d
",dis[ss]);
44 }
45 void print (int u,int v    ) 
46 {
47     int tot=1;
48     que[tot]=v;
49     tot++;
50     int temp=qq[v];
51     while(temp!=u)
52       {    que[tot]=temp;
53         tot++;
54         temp=qq[temp];
55       }
56     que[tot]=u;
57     for(int i=tot;i>=1;i--)
58          if(i!=1)
59              printf("%d->",que[i]);
60          else
61              printf("%d",que[i]);
62 
63 }
64 int main()
65 {    
66     scanf("%d%d",&n,&m);
67     memset(dis,MAXX,sizeof(dis));
68     memset(map,MAXX,sizeof(map));
69     for(int i=1;i<=m;++i)
70     {
71         int x,y,q;
72         scanf("%d%d%d",&x,&y,&q);
73         map[x][y]=q;
74         map[y][x]=q;    
75     }
76     scanf("%d%d",&s,&ss);
77     work(s);
78     print(s,ss);
79     return 0;
80 }

 
転載先:https://www.cnblogs.com/mjtcn/p/6686148.html