此篇文章部分内容转载自Ciel的文章

传送门：最短路算法 ( By Ciel)

---

Floyd 算法：

Floyd算法运用动态规划的思想，枚举顶点i和j并枚举第三个点—k，看是否有一顶点k使i到k再到j的路径长度小于当前i到j的路径长度，如果有，则用map[i][k]+map[k][j]更新map[i][j]的值。

5行巨短代码决定了它的时间复杂度O(n^3)

for(k=1;k<=n;k++)
	for(i=1;i<=n;i++)			
		for(j=1;j<=n;j++)
			if(map[i][k]+map[k][j]<map[i][j])
				map[i][j]=map[i][k]+map[k][j];

---

Dijkstra算法：

通常地，我们使用邻接表来存储图，方便Dijkstra算法的实现。

Dijkstra算法定义数组f[i]的值为目前认为最优的从出发点到点i的最短路径长度，初始时f[出发点]为0(到本身不需要路径)，其他为无穷大；

定义数组v[i]表示当前结点的路径长度是否已是最优，初始全为false。

接下来，找出一个使v[i]为且f[i]尽可能小的i，把v[i]标记为true，认为其现在的解已达到最优，并循环其所有出边，优化这些出边的到达点的最短路径。然后重复做下去，一共做n次。

邻接矩阵实现：

void dijkstra()
{
    memset(dis,0x3f,sizeof dis);
    memset(book,0,sizeof book);
    dis[1]=0;
    for(int i=1;i<=n;i++)
    {
		int u,min=0x3f3f3f3f;
        for(int j=1;j<=n;j++)
        {
            if(book[j]==0&&dis[j]<min)  
            {
                min=dis[j],u=j;
            }
        }
        book[u]=1;
        for(int v=1;v<=n;v++)
        {
            if(dis[v]>dis[u]+f[u][v]) 
            {
                dis[v]=dis[u]+f[u][v];
                path[v]=u;//记录路径 
            }
        }
    }
}

 

链表实现：

void dijkstra()
{
	memset(dis,0x3f,sizeof dis);
	memset(book,0,sizeof book);
	dis[1]=0;
	for(int i=1;i<=n;i++)
	{
		int u,minn=0x3f3f3f3f;
		for(int j=1;j<=n;j++)
		{
			 if(book[j]==0&&minn>dis[j])
			 {
			 	minn=dis[j],u=j;
			 }
		}
		book[u]=1;
		for(int j=head[u];j!=0;j=next[j])
		{
			if(dis[to[j]]>dis[u]+v[j])
			{
				dis[to[j]]=dis[u]+v[j];
				path[to[j]]=u;//记录路径 
			}	
		}
	}
}
void add(int x,int y,int val)
{ 
	tot++;
	v[tot]=val;
	to[tot]=y;
	next[tot]=head[x];
	head[x]=tot;
}

---

Spfa 算法：

通常地，我们使用邻接表来存储图，方便SPFA的实现。
SPFA定义数组f[i]的值为目前认为最优的从出发点到点i的最短路径长度，初始时f[出发点]为0(到本身不需要路径)，其他为无穷大；
然后建立一个队列，存放将被用来优化其他结点最短路径的结点，初始只有一个出发点；
定义数组v[i]表示当前结点是否在队列中，初始时v[出发点]为1，其他为0。
接下来，取出队列中队首元素，枚举其全部出边，优化出边到达的节点。如果能够更新一个不在队列中的结点i（v[i]==0），则将其加入节点，稍后以其为基础优化它的出边所到达的结点。这样做直到没有节点可以被用来优化，也就是队列为空时停止。

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int f[2000100],n,m,a,b,r,top;
int to[2000100],value[2000100],next[2000100],head[2000100];
bool book[1000100];
void spfa()
{
    queue<int> q;
    memset(f,0x3f,sizeof f);
    q.push(1);
    f[1]=0;
    book[1]=true;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        book[x]=false;
        for(int i=head[x];i!=0;i=next[i])
        {
            if(f[to[i]]>f[x]+value[i])
            {
                f[to[i]]=f[x]+value[i];
                if(!book[to[i]])
                {
                    q.push(to[i]);
                    book[to[i]]=true;
                }
            }
        }
    }
}
void add(int x,int y,int v)
{
    ++top;
    to[top]=y;
    value[top]=v;
    next[top]=head[x];
    head[x]=top;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a,&b,&r);
        add(a,b,r);
        add(b,a,r);
    }   
    spfa();
    printf("%d",f[n]);
}