C++ 教程

最短路径

问题描述:

在一个图中,求从s到t的最短路径

解决办法

方法一:弗洛伊德法

介绍:
这是最简单的方法,时间复杂度为n^3
代码:

for(int k=1;k<=n;k++)    //枚举中间点
    for(int i=1;i<=n;i++)    //枚举起点
        for(int j=1;j<=n;j++)    //枚举终点
            diss[i][j]=min(diss[i][j],diss[i][k]+diss[k][j]);    //diss[i][j]表示i到j的距离(权值)

运行完后直接读取你需要的diss[s][t]

方法2:bellman-ford

介绍:

代码:

void ford()
{
    d[s]=0;    //s是起点
    for(int i=1;i

读取d[t]
运行完后读取你想要的

方法4:spfa

特别之处:
可以处理含有负权值的图
代码:

void spfa()
{
    q.push(s);    //s是起点
    vis[s]=1;
    d[s]=0;
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=h[u];i;i=nxt[i])
        {
            int v=to[i];
            double w=val[i];
            if(d[v]

读取你要的d[t]

方法3:Dijkastra

特别之处:
只能处理正权值,但速度快且稳定,必须确定起点在哪
代码:

void dijkstra(int s)//输入起点
{
    d[s]=0;
    for(int i=1;i<=n;i++)
    {
        int k=0;
        for(int j=1;j<=n;j++)
          if(!vis[j]&&(d[j]

运行完后读取你需要的d[s]