最短回路アルゴリズムテンプレート(dijkstra+floyd+spfa)

1.Floyd_Warshallアルゴリズム
参考:『チャレンジプログラミングコンテスト』およびhttps://blog.csdn.net/Floraqiu/article/details/81483420コア構想:d[i][j]=min{d[i][j],d[i][k]+d[k][j]}iからjまでの2つの経路があり、k点を通過するかk点を通過しないので、kを列挙するとすべての道の最短ルートを求めることができる.適用範囲:任意の2点の間の最短ルートを求めて、負の権力があることができて、有向図が無方向図であることができて、しかしnは必ず200以内でなければなりません

#include 
#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f

using namespace std;

int main()
{
    int n, m, s, t;
    while(~scanf("%d%d", &n, &m))
    {
        vector<vector<int> > dis(n);//vector       
        for(int i = 0; i < n; i++)
        {
            dis[i].resize(n, INF);//     dis[i]   ，  INF     
            dis[i][i] = 0;
        }
        for(int i = 0; i < m; i++)//   a,b      x
        {
            int a, b, x;
            scanf("%d%d%d", &a, &b, &x);
            if(dis[a][b] > x)
                dis[a][b] = dis[b][a] = x;
        }
        scanf("%d%d", &s, &t);
        for(int k = 0; k < n; k++)
            for(int i = 0; i < n; i++)
                for(int j = 0; j < n; j++)
                {
                    if(dis[i][k] < INF && dis[k][j] < INF)
                        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
        if(dis[s][t] != INF)//           
            printf("%d
", dis[s][t]);
        else
            printf("-1
");
    }
    return 0;
}

2.Dijkstraアルゴリズム
参考:アルゴリズムコンテスト入門クラシックとhttps://blog.csdn.net/Floraqiu/article/details/81484870コア構想:D(s,t)={Vs...Vi...Vj...Vt}はsからtの最短路を表し、iとjがこの経路上の2つの中間ノードである場合、D(i,j)は必ずiからjの最短路であり、このような最短路D(s,t)={Vs...Vi Vt}が存在し、iとtが最短路上で隣接する点である場合、D(s,i)={Vs...Vi}は必ずsからiの最短路である.Dijkstraアルゴリズムは,このような性質に基づいて,最短経路長をインクリメントすることにより,徐々に最短経路を生成する.適用状況:正権図上のユニットが最短、有向図無向図、単一ソース点からすべてのノードまでの最短

     s
        
 dis[s] = 0,  dis[i] = INF
  n 
{ 
             ，  dis      X
      X  
      X        y，  dis[y] = min{dis[y], dis[x]+w(x,y)}
}

隣接マトリクスの実装:

void dijkstra(int s)//s   
{
    memset(dis, INF, sizeof(dis));
    memset(vis,0,sizeof(vis);
    vis[s] = 1;
    dis[s] = 0;
    for(int i = 1; i <= n; i++)//  n-1 
    {
        int min_dis = INF;
        int x;
        for(int j = 1; j <= n; j++)//                  x
        {
            if(!vis[j] && min_dis > dis[j])
            {
                x = j;
                min_dis = dis[j];
            }
        }
        vis[x] = 1;//   X         
        for(int j = 1; j <= n; j++)//            
        {
            if(!vis[j])
                dis[j] = min(dis[j], dis[x] + mapp[x][j]);//x j   +dis[x]
        }
    }
}

優先キュー最適化版

#include 
#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f

using namespace std;
const int maxn = 105;
int dis[maxn], pre[maxn];

struct Edge//  
{
    int u, v, w;
    Edge() {};
    Edge(int uu, int vv, int ww): u(uu), v(vv), w(ww) {};
};

vector<Edge> edges;//    
vector<int> G[maxn];//              


void init(int nn)//   
{
    for(int i = 0; i <= nn; i++)
        G[i].clear();
    edges.clear();
}

void AddEdge(int uu, int vv, int ww)//   
{
    edges.push_back(Edge(uu, vv, ww));
    int edgenum = edges.size();
    G[uu].push_back(edgenum - 1);
}

struct node//      ，dis      
{
    int u, d;
    node() {};
    node(int uu, int dd): u(uu), d(dd) {};
    friend bool operator < (node a, node b)
    {
        return a.d > b.d;
    }
};

void dijkstra(int s)
{
    priority_queue<node> q;
    memset(dis, INF, sizeof(dis));//dis    INF 
    dis[s] = 0;
    q.push(node(s, dis[s]));
    while(!q.empty())
    {
        node cur = q.top();
        q.pop();
        int from = cur.u;
        if(cur.d != dis[from])//   vis  ，           
            continue;
        for(int i = 0; i < G[from].size(); i++)//            dis 
        {
            Edge e = edges[G[from][i]];
            if(dis[e.v] > dis[e.u] + e.w)
            {
                dis[e.v] = dis[e.u] + e.w;
                pre[e.v] = from;//      
                q.push(node(e.v, dis[e.v]));//     dis       
            }
        }
    }
}
int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m) && n && m)
    {
        init(n);
        for(int i = 0; i < m; i++)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            AddEdge(u, v, w);
            AddEdge(v, u, w);
        }
        dijkstra(1);
        printf("%d
", dis[n]);
    }
    return 0;
}

3.SPFAアルゴリズム
核心構想:https://blog.csdn.net/qq_35644234/article/details/61614581最適化対象のノードを保存するために先進的な先頭のキューを設定し、最適化時にキューヘッダuを取り出すたびに、u点から離れるノードvをu点の現在の最短経路推定値で緩和操作し、v点の最短経路推定値が調整され、v点が現在のキューにない場合、v点をキューの最後に入れる.このようにキューからノードを取り出して緩和操作を行い、キューが空になるまで適用する:正の重みが負の重みを持つことができ、有向図が無方向図であり、単一のソース点からすべてのノードの最短路まで
コード参照:https://blog.csdn.net/Since_natural_ran/article/details/52955460

#include
#include
#include
#include
#include
 
#define inf 0x3f3f3f3f
 
using namespace std;
 
int dis[105],visit[105];
int n,m;
 
class Node
{
public:
    int e,v;
    Node(int a,int b){e = a,v = b;}
};
 
vector<Node>s[105];
 
void spfa()
{
    memset(dis,inf,sizeof(dis));
    memset(visit,0,sizeof(visit));
    dis[1] = 0;
    queue<int>q;
    q.push(1);
    visit[1] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        visit[u] = false;
        int num = s[u].size();
        for(int i = 0;i < num; i++){
            if(dis[u] + s[u][i].v > dis[s[u][i].e])
                continue;
            dis[s[u][i].e] = dis[u] + s[u][i].v;
            if(!visit[s[u][i].e]){
                q.push(s[u][i].e);
                visit[s[u][i].e] = true;
            }
        }
    }
}
 
int main()
{
 //   freopen("in.txt","r",stdin);
    while(cin>>n>>m){
        if(n == 0 && m == 0)
            break;
        for(int i = 1;i <= n; i++)
            s[i].clear();
        int a,b,c;
        for(int i = 1;i <= m; i++){
            cin>>a>>b>>c;
            s[a].push_back(Node(b,c));
            s[b].push_back(Node(a,c));//    
        }
        spfa();
        cout<<dis[n]<<endl;
    }
    return 0;
}