图论Graph Theory（2）：最短路径

最短路径

• • • 一、单源最短路径问题
    • • 1.1 Dijkstra算法（不可处理负边）
      • • • 边权值存在邻接矩阵中
          • 边权值存在邻接表中
      • 1.2 Bellman-ford算法
      • 1.3 SPFA
    • 二、多源多目标的最短路径问题
    • • 2.1 Floyd-Warshall 算法

一、单源最短路径问题

从一个顶点到其他所有顶点间的最短路径

1.1 Dijkstra算法（不可处理负边）

边权值存在邻接矩阵中

//TSWorld
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
using namespace std;
const int N = 10005;
const int MAXX = 0x3ffffff;

vector<int>edge[N];
int map[N][N];
int dis[N];
bool vis[N];
void dijstra(int s,const int n){
    
    int u=0,minn_weight=0;
    for(int i=1;i<=n;i++)
        dis[i]=map[s][i];

    dis[s]=0;
    vis[s]=true;

    for(int i=1;i<n;i++){
        minn_weight=MAXX;
        for(int j=1;j<=n;j++){
            if((!vis[j])&&(dis[j]<minn_weight))
            {
                u=j;
                minn_weight=dis[j];
            }
        }

        vis[u]=true;

        for(int j=0;j<edge[u].size();j++){
            if((!vis[edge[u][j]])&&(dis[edge[u][j]]>dis[u]+map[u][edge[u][j]]))
                dis[edge[u][j]]=dis[u]+map[u][edge[u][j]];
        }
    }
    return;
}
int main()
{
    int n=0,m=0,s=0;
    int u=0,v=0,weight=0;
    const int wrong = pow(2,31)-1;
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            map[i][j]=MAXX;

    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&weight);
        edge[u].push_back(v);
        map[u][v]=weight;
    }
    dijstra(s,n);
    for(int i=1;i<=n;i++){
        if(dis[i]!=MAXX)
            cout<<dis[i]<<" ";
        else
            cout<<wrong<<" ";
    }
    return 0;
}
           

边权值存在邻接表中

//TSWorld
#include<bits/stdc++.h>
using namespace std;
const int MAXN=10001;
const int inf=2139062143;
struct Edge
{
    int end,value;
    Edge(int e,int v):end(e),value(v){}
};
int n,m,s;
vector<Edge> g[MAXN];
int dis[MAXN];
bool vis[MAXN];
void Dijkstra(int & st)
{
    memset(dis,0x7f,sizeof(dis));
    dis[st]=0;
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        int Min=inf;
        for(int j=1;j<=n;j++)
            if(vis[j]==false&&(Min==inf||dis[j]<dis[Min]))
                Min=j;
        if(Min==inf)
            return;
        vis[Min]=true;
        for(vector<Edge>::iterator iter=g[Min].begin();iter!=g[Min].end();iter++)
            if(vis[iter->end]==false)
                dis[iter->end]=min(dis[iter->end],dis[Min]+iter->value);
    }
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back(Edge(y,z));
    }
    Dijkstra(s);
    for(int i=1;i<=n;i++)
        if(i==1)
            cout<<(dis[i]==inf?0x7fffffff:dis[i]);
        else
            cout<<" "<<(dis[i]==inf?0x7fffffff:dis[i]);
    cout<<endl;
    return 0;
}
           

1.2 Bellman-ford算法

//TSWorld
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int N = 10005;
const int MAXX = 0x3fffff;
struct Edge{
	int to;		
	int en;
	int weight;
};

struct Graph {
	int V;
	int E;
	struct Edge *edge;
};
struct Graph *creatGraph(int V,int E) {
	struct Graph * graph = new Graph;
	graph->V = V;
	graph->E = E;
	graph->edge = new Edge[E];
	return graph;
};
void print (int dist[],int V) {
	for(int i=1;i<=V;i++)
		cout<<dist[i]<<" ";
	return;
}
void Bellman_ford(struct Graph* graph,int s) {
	int V = graph->V;
	int E = graph->E;
	int dist[V+5];

	for (int i=1;i<=V;i++) 
		dist[i] = MAXX;
	dist[s] = 0;

	for (int i = 1;i < V;i++) {
		for (int j = 0;j < E;j++) {
			int u = graph->edge[j].to;
			int v = graph->edge[j].en;
			int weight = graph->edge[j].weight;
			if (dist[u] != MAXX && dist[v] > dist[u] + weight) {
				dist[v] = dist[u] + weight;
			}
		}
	}
	print (dist,V);
	return;
}
int main()
{
	int n=0,m=0,s=0;
	cin>>n>>m>>s;
	struct Graph* graph = creatGraph(n,m);

	for(int i=0;i<m;i++){
		cin>>graph->edge[i].to>>graph->edge[i].en>>graph->edge[i].weight;
	}

	Bellman_ford(graph,s);
	return 0;
}
           

1.3 SPFA

SPFA是Bellman-Ford算法的改进，在1-n-1的循环中，只有被修改的点才会更新，所以造成了很多没有必要的操作，SPFA算法利用队列提高了效率

//TSWorld
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int N = 10005;

struct Edge
{
	int dest;
	int weight;
	Edge(int v,int w):dest(v),weight(w){}
};
vector<Edge>edge[N];

void SPFA(int src,int n)
{
	int dis[N];
	bool vis[N];
	queue<int>subqueue;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,false,sizeof(vis));
	dis[src] = 0;
	vis[src] = true;
	subqueue.push(src);

	while(!subqueue.empty())
	{
		int v = subqueue.front();
		subqueue.pop();
		vis[v] = false;
		for(int i=0;i<edge[v].size();i++) {
			int u = edge[v][i].dest;
			if(dis[u]>dis[v]+edge[v][i].weight) {
				dis[u] = dis[v]+edge[v][i].weight;
				if(!vis[u]) {
					subqueue.push(u);
					vis[u] = true;
				}
			}
		}
	}

	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
}
int main()
{
	int n = 0,m = 0;
	int src = 0;
	int u = 0,v = 0,weight = 0;
	cin>>n>>m>>src;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>weight;
		edge[u].push_back(Edge(v,weight));
	}

	SPFA(src,n);
	return 0;
}
           

二、多源多目标的最短路径问题

2.1 Floyd-Warshall 算法

//TSWorld
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int N = 10009;
const int inf = 0x3ffffff;
int dist[N][N];

int main(){
	int n=0,m=0;
	int u=0,v=0,w=0;

	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dist[i][j] = inf;

	for(int i=1;i<=n;i++)
		dist[i][i] = 0;

	for(int i=1;i<=m;i++) {
		cin>>u>>v>>w;
		dist[u][v] = w;
	}

	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++) {
				if(dist[i][j]>dist[i][k] + dist[k][j])
					dist[i][j] = dist[i][k] + dist[k][j];
			}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) 
			cout<<dist[i][j]<<" ";
		cout<<endl;
	}
	return 0;
}