最短路 POJ2387

第一种迪杰斯特拉算法求最短路（时间复杂度为（n*n））

要求边的权值为正数

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 int t,n;
 8 int map[1010][1010];
 9 bool vis[1010];
10 int div[1010];
11 int MAX=1<<29;
12 
13 int main()
14 {
15     while(scanf("%d%d",&t,&n)!=EOF)
16     {
17         for(int i=1;i<=n;i++)
18         {
19             for(int j=1;j<=n;j++)
20             {
21                 if(i==j)
22                     map[i][j]=0;
23                 else
24                     map[i][j]=map[j][i]=MAX;
25             }
26         }
27         int fro,to,val;
28         for(int i=0;i<t;i++)
29         {
30             scanf("%d%d%d",&fro,&to,&val);
31             if(map[fro][to]>val)
32                 map[fro][to]=map[to][fro]=val;
33         }
34         memset(vis,false,sizeof(vis));
35         for(int i=1;i<=n;i++)
36         {
37             div[i]=map[1][i];
38         }
39         for(int i=1;i<=n;i++)
40         {
41             int mi=MAX;
42             int v;
43             for(int j=1;j<=n;j++)
44             {
45                 if(!vis[j]&&div[j]<mi)
46                 {
47                     mi=div[j];
48                     v=j;
49                 }
50             }
51             vis[v]=true;
52             for(int j=1;j<=n;j++)
53             {
54                 if(!vis[j]&&div[v]+map[v][j]<div[j])
55                 {
56                     div[j]=div[v]+map[v][j];
57                 }
58             }
59         }
60         cout<<div[n]<<endl;
61     }
62     return 0;
63 }

View Code

第二种贝尔曼福德算法（时间复杂度为（n*m））

边的权值可以为负数，并且可以判断图中是否有负环

1　　图的初始化等操作

2　　for i = 1 to |G.V| - 1 // |G.V| 为图 G的点的总数

3　　　　for each edge(u,v)∈G.E //G.E 为图 G 的边

4 　　　　relax(u,v,w) 也就是if v.d>u.d+w(u,v) ， v.d = u.d+w(u,v);

5　　for each edge(u,v)∈G.E

6 　　　　if v.d>u.d+w(u,v) //v.d为出发源点到结点v的最短路径的估计值 u.d亦如此 w(u,v) 为u结点到v结点的权重值(通俗点就是u—>v的花费)。

7　　　　　　return false;

8　　return true

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 int MAX=1<<29;
 8 struct node
 9 {
10     int fro,to,val;
11 }bn[2010];
12 int t,n;
13 int div[1010];
14 
15 int main()
16 {
17     while(scanf("%d%d",&t,&n)!=EOF)
18     {
19         for(int i=1;i<=t;i++)
20         {
21             scanf("%d%d%d",&bn[i].fro,&bn[i].to,&bn[i].val);
22         }
23         div[1]=0;
24         for(int i=2;i<=n;i++)
25             div[i]=MAX;
26         for(int i=1;i<=n;i++)
27         {
28             for(int j=1;j<=t;j++)
29             {
30                 if(div[bn[j].fro]>div[bn[j].to]+bn[j].val)
31                     div[bn[j].fro]=div[bn[j].to]+bn[j].val;
32                 if(div[bn[j].to]>div[bn[j].fro]+bn[j].val)
33                     div[bn[j].to]=div[bn[j].fro]+bn[j].val;
34             }
35         }
36         cout<<div[n]<<endl;
37     }
38     return 0;
39 }

View Code

第三种spfa算法

const int MAXN=1010;
const int MAXM=20010;
int tot;
const long long INF=1e11;
int head[MAXN];
bool vis[MAXN];
int cnt[MAXN];
long long dist[MAXN];

struct Edge
{
    int to;
    int cost;
    int next;
}edge[MAXM];

void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
}

void addedge(int u,int v,int w)
{
    edge[tot].to=v;
    edge[tot].cost=w;
    edge[tot].next=head[u];
    head[u]=tot++;
}

bool SPFA(int start,int n)
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        dist[i]=INF;
    }
    vis[start]=true;
    dist[start]=0;
    queue<int>que;
    while(!que.empty())
        que.pop();
    que.push(start);
    memset(cnt,0,sizeof(cnt));
    cnt[start]=1;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(dist[v]>dist[u]+edge[i].cost)
            {
                dist[v]=dist[u]+edge[i].cost;
                if(!vis[v])
                {
                    vis[v]=true;
                    que.push(v);
                    if(++cnt[v]>n)
                        return false;
                }
            }
        }
    }
    return true;
}