最短路算法模板合集（Dijkstar，Dijkstar（优先队列优化），多源最短路Floyd）

再开始前我们先普及一下简单的图论知识

图的保存：

1.邻接矩阵。 G[maxn][maxn];

2.邻接表

邻接表我们有两种方式

（1）vector< Node > G[maxn];

这个是之前就定义了图的大小了，再下面使用的时候就不用对图的大小进行申请了，但是因为是直接申请了大小

要对图进行初始化，因此可能在某些题目中这样使用的话会超时

（2）vector< vector<Node> > G;

这个是未定义大小，但是在使用之前要对其的大小内存进行申请。

G.resize(n+1);

Dijkstra's Algorithm

算法思想：

1.从源点出发源点所有能一步到达的点的距离更新，然后从除源点外的所有点之中找出距离源点最近的点。

2.然后更新我们之前所找到的最短路点所有连接的点，但是要求这个点未曾被当做最短点处理过

3.重复上述操作n次。

单源最短路我们还可以对他进行优先队列优化下面是以HDU2544为模板的用Dijkstra's Algorithm

邻接矩阵版，不用优先队列优化

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define INF 0xfffffff
#define maxn 1002

int G[maxn][maxn];//保存图
int dist[maxn];//表示从起点到第i点的距离
bool vis[maxn];//判断这个点是否被参观过
int m, n;//边数 m   顶点数 n

void Init()
{
    for(int i=0; i<=n; i++)
    {
        vis[i] = false;
        dist[i] = INF;
        for(int j=0; j<=i; j++)
            G[i][j] = G[j][i] =  INF;
    }
}
int Dij(int Star,int End)//起点 --- 终点
{
    dist[Star] = 0;
    for(int i=1; i<=n; i++)
    {
        int index = 0, Min = INF;
        for(int j=1; j<=n; j++)
        {
            if( !vis[j] && Min > dist[j] )//找出没有被参观过，并且距离起点最近的点
                Min = dist[j], index = j;
        }

        vis[index] = true;

        for(int j=1; j<=n; j++)//更新所有未曾到达的点距离，使之成为最近的点
        {
            if( !vis[j] && dist[j] >  dist[index] + G[index][j] )
                dist[j] = dist[index] + G[index][j];
        }
    }

    return dist[End];

}

int main()
{
    while(cin >> n >> m, m + n)
    {
        Init();

        int a, b , c;

        for(int i=0; i<m; i++)
        {
            cin >> a >> b >> c;
            G[a][b] = min(G[a][b], c);
            G[b][a] = G[a][b];
        }

        int ans = Dij(1,n);

        cout << ans << endl;
    }
    return 0;
}

　　接下来是邻接表版，用到了优先队列优化

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cstdio>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <queue>
 9 using namespace std;
10 #define INF 0xfffffff
11 #define maxn 1002
12 
13 struct Node
14 {
15     int e;
16     int w;
17     friend bool operator < (Node A, Node B)
18     {
19         return  A.w > B.w;
20     }
21 };
22 
23 bool vis[maxn];
24 
25 int m, n;
26 vector< vector<Node> > G;
27 
28 int Dij(int Star,int End)
29 {
30     Node P, Pn;
31     P.e = Star;
32     P.w = 0;
33 
34     priority_queue<Node> Q;
35 
36     Q.push(P);
37 
38     while( !Q.empty() )
39     {
40         P = Q.top();
41         Q.pop();
42 
43         if( vis[P.e] )
44             continue;
45 
46         vis[P.e] = true;
47 
48         if( P.e == End )
49             return P.w;
50 
51         int len = G[P.e].size();
52 
53         for(int i=0; i< len; i++)
54         {
55             Pn.e = G[P.e][i].e;
56             Pn.w = G[P.e][i].w + P.w;
57 
58             if( !vis[Pn.e] )
59                 Q.push(Pn);
60         }
61     }
62     return -1;
63 }
64 
65 int main()
66 {
67     Node P;
68     while(cin >> n >> m, m+n)
69     {
70         G.clear();
71         G.resize(n+1);
72 
73         memset(vis,false,sizeof(vis));
74 
75         for(int i=0; i<m; i++)
76         {
77             int a, b, c;
78             cin >> a >> b >> c;
79             P.e = b;
80             P.w = c;
81             G[a].push_back(P);
82             P.e = a;
83             G[b].push_back(P);
84         }
85 
86         int ans = Dij(1,n);
87 
88         cout << ans << endl;
89     }
90     return 0;
91 }

下面是Floyd算法

Floyd是求多源最短路，即可以求出所有点对之间的最短路

这个算法就只要注意两点就行了，初始化的时候 G[i][i] = 0, 其他的初始化为INF

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define INF 0xfffffff
#define maxn 1002

int G[maxn][maxn];
int dist[maxn][maxn];
int m, n;

void Floyd()
{
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
            }
        }
    }
}
void Init()
{
    for(int i=0; i<=n; i++)
    {
        G[i][i] = 0;
        for(int j=0; j<i; j++)
            G[i][j] = G[j][i] = INF;
    }
}

int main()
{
    while(cin >> n >> m, m+n)
    {
        Init();
        for(int i=0; i<m; i++)
        {
            int a, b, c;
            cin >> a >> b >> c;
            G[a][b] = min(G[a][b],c);
            G[b][a] = G[a][b];
        }

        Floyd();

        cout << G[1][n] << endl;
    }
    return 0;
}

最短路算法模板合集（Dijkstar，Dijkstar（优先队列优化）， 多源最短路Floyd）

最短路算法模板合集（Dijkstar，Dijkstar（优先队列优化），多源最短路Floyd）