Dijkstra[2つの隣接テーブル+優先キュー最適化]

4602 ワード

Dijkstaアルゴリズムでは,隣接行列を用いて保存する場合,第1点の無駄な空間が多く,第2点はアルゴリズムの時間的複雑度がO(n*n)であることを知っているが,このようなアルゴリズムはあまりよくないと言えるので,まず記憶構造を最適化し,隣接テーブルを用いて記憶することができ,次に優先キューでサイズをソートすることができることを考慮した.その時間的複雑さは大幅に低下した.
注意すべきはpairが最初の要素の大きさでソートされ、同じ場合には2番目にソートされるので、d[i]を最初の要素に包装します.
vectorは隣接テーブル+優先キューを実現する(エッジが最初は文字型であると仮定し、難易度を上げるためであると仮定する)

#include
#include
#include
#include
#include
#include
#include
#define inf 0x7fffffff
using namespace std;
const int MAXN = 205;
int dis[MAXN];
int n;  //    
int m;  //    
string src,ed; //src   ，ed    
typedef pair pii;
struct edge //       
{
    int u;
    int v;
    int w;
    edge(int a,int b,int c) //    ，                ，         。
    {
        u = a;
        v = b;
        w = c;
    }
};
mapM; //  map               
vector G[MAXN];//   
void init()
{
    M.clear();//      map  
    int cnt=0;
    cin>>n>>m;
    string u,v;//     
    int w;//  
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        if(!M.count(u))
            M.insert(make_pair(u,++cnt));  //make_pair      pair<>        map，vector    
        if(!M.count(v))
            M.insert(make_pair(v,++cnt));   //  map               ,1,2,3...  A    1  ，       1  。
        edge E1(M[u],M[v],w);  //     ，      ，  。
        edge E2(M[v],M[u],w);
        G[M[u]].push_back(E1); //     
        G[M[v]].push_back(E2);
    }
    cin>>src>>ed;
    for(int i =1;i<=n;i++) dis[i] = (i == M[src] ? 0 : inf);//   dis
}
void dijktra()
{
    priority_queue,greater > que;
    que.push(make_pair(0,M[src]));//       ，pair       first  ，                   dis[]  
    while(!que.empty())
    {
        pii tmp = que.top();
        que.pop();
        int x = tmp.second;
        if(tmp.first != dis[x]) continue;     //          ，                      ，         ，
                                           //   dis,    dis   ，            ,                      。
        for(int  i = 0;i < G[x].size();i++)
        {
            int y = G[x][i].v;
            int w = G[x][i].w;
            if(dis[y] > dis[x] + w)
            {
                dis[y] = dis[x] + w;
                que.push(make_pair(dis[y],y));
            }
        }
    }
}
int main()
{
   // freopen("1.in","r",stdin);
    int _;
    cin>>_;
    while(_--){
        init();
        dijktra();
        if(dis[M[ed]]==inf) cout<::iterator it=M.begin();it!=M.end();it++) printf("%d ",dis[it->second]);
        putchar('
');
    }
    return 0;
}

入力データ:
1
6 9
D E 13
B C 9
A B 1
A C 12
B D 3
E C 5
D C 4
D F 15
E F 4
A F
出力データ:
17
0 1 8 4 13 17
配列実装隣接テーブル+優先キュー

#include
#include
#include
#include
#define inf 0x7fffffff
using namespace std;
const int MAXN = 205;
int dis[MAXN];
int u[MAXN],v[MAXN],w[MAXN];
int first[MAXN],next[MAXN];
int n,m;
int src,ed;
typedef pair pii;
void init()
{
    scanf("%d%d",&n,&m);
    memset(first,-1,sizeof(first));
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u[i],&v[i],&w[i]);
        next[i]=first[u[i]];
        first[u[i] ]=i;
        u[i+m]=v[i],v[i+m]=u[i],w[i+m]=w[i];  //   ，        
        next[i+m]=first[u[i+m] ];
        first[u[i+m] ]=i+m;
    }
    cin>>src>>ed;
    for(int i=1;i<=n;i++) dis[i]= (i==src? 0:inf);//   dis[i]              ，        。
}
void dijkstra()
{
    priority_queue,greater >que;
    que.push(pii(0,src));
    while(!que.empty()){
        pii tmp=que.top();
        que.pop();
        int x = tmp.second;
        if(tmp.first!=dis[x]) continue;  //         ,   dis,    dis   ，                   ，
        for(int e=first[x];e!=-1;e=next[e]){   //           
            if(dis[v[e]]>dis[x]+w[e]){
                 dis[v[e] ]=dis[x]+w[e];
                 que.push(pii(dis[v[e] ],v[e]));
            }
        }
    }

}
int main()
{
 //   freopen("1.in","r",stdin);
    int _;
    scanf("%d",&_);
    while(_--){
        init();
        dijkstra();
        if(dis[ed]==inf) cout<

テストデータ:
1
6 9
1 2 1
1 3 12
2 3 9
2 4 3
5 3 5
4 3 4
4 5 13
4 6 15
5 6 4
1 6
出力:
17
0 1 8 4 13 17

K-近隣アルゴリズム

でんしん