最短路问题

标签：存储 dist int 短路 问题 算法 quad 号点

\[最短路 \begin{cases} \ 单源最短路 \quad \begin{cases}\ 所有边权都是正数 \quad \begin{cases}\ 朴素Dijkstra算法 \quad \\[3ex] 堆优化版Dijkstra算法 \quad \end{cases}\ \\[5ex] 存在负权边 \quad \begin{cases}\ Bell-Ford算法 \quad \\[3ex] SPFA算法 \quad \end{cases}\ \end{cases}\ \\[7ex] 多源汇最短路 \quad Floyd算法 \end{cases}\ \]

---

朴素Dijkstra算法

朴素Dijkstra 基本思想：

集合 s 存储当前已确定最短距离的点

①dist [ 1 ] = 0 , dist [ i ] = + $ \infty $

②迭代\(\quad\)\(\quad\)for i : 1 ~ n

\(\quad\)\(\quad\)\(\quad\)​\(\quad\)\(\quad\)\(\quad\)t \(\gets\) 不在s中的, 距离最近的点

\(\quad\)\(\quad\)\(\quad\)​\(\quad\)\(\quad\)\(\quad\)s \(\gets\) t

\(\quad\)\(\quad\)\(\quad\)​\(\quad\)\(\quad\)\(\quad\)用t更新其他点

边的存储方式

• 稠密图 —— 邻接矩阵
• 稀疏图 —— 邻接表

//朴素Dijkstra算法模板

int g[N][N];	//存储每条边
int dist[N];	//存储1号点到每个点的最短距离
bool st[N];		//存储每个点的最短路是否已确定

//求1号点到n号点的最短路,如果不存在则返回-1
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    
    for(int i=0;i<n;i++)
    {
        int t=-1;	//在还未确定最短路的点中,寻找距离最小的点
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        
        //用t更新其他点的距离
        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        
        st[t]=true;
    }
    
    if(dist[n]==0x3f3f3f3f)return -1;
    return dist[n];
}

---

堆优化版Dijkstra算法

//堆优化版Dijkstra算法模板
typedef pair<int,int> PII;

int n;		//点的数量
int h[N],w[N],e[N],ne[N],idx;	//邻接表存储所有边
int dist[N];		//存储所有点到1号点的距离
bool st[N];			//存储每个点的最短路是否已确定

//邻接表存储所有边
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

//求1号点到n号点的最短距离,如果不存在则返回-1
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue <PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1});
    
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.second,distance=t.first;
        
        if(st[ver])continue;
        st[ver]=true;
        
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>distance+w[i])
            {
                dist[j]=distance+w[i];
                heap.push({dist[j],j});
            }
        }
    }
    
    if(dist[n]==0x3f3f3f3f)return -1;
    return dist[n];
}

---

Bellman - Ford算法

Bellman - Ford算法基本思想:

迭代\(\quad\)\(\quad\)for n次 (迭代k次,表示经过不超过k条边)

​\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)for 所有边a, b, w \(a \stackrel{w}{\rightarrow} b\)

\(\quad\)\(\quad\)​\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)dist[b] = min (dist[b] , dist[a] + w)

//Bell-Ford算法模板

int n,m,k;		//n表示点数,m表示边数,k表示经过不超过k条边
int dist[N];	//dist[x]用于存储1到x的最短距离
int backup[N];	//backup[x]用于备份数组dist[N]

Struct Edge		//存储边
{
    int a,b,w;
}edge[N];

//求1到n经过不超过k条边的最短路距离,如果无法从1走到n则返回-1
int bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    
    for(int i=0;i<k;i++)
    {
        memcpy(backup,dist,sizeof dist);
        
        for(int j=0;j<m;j++)
        {
            int a=edges[i].a,b=edges[i].b,w=edges[i].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }
    
    if(dist[n]>0x3f3f3f3f/2)return -1;
    return dist[n];
}

---

SPFA算法

//spfa算法模板

int n;		//总点数
int h[N],w[N],e[N],ne[N],idx;		//邻接表存储所有边
int dist[N];		//存储每个点到1号点的最短距离
bool st[N];			//存储每个点是否在队列中

//邻接表存储所有边
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

//求1号点到n号点的最短路距离,如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    
    queue<int>q;
    q.push(1);
    st[1]=true;
    
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!st[j])	//如果队列中已存在j,则不需要将j重复插入
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    
    if(dist[n]==0x3f3f3f3f)return -1;
    return dist[n];
}

//spfa判断图中是否存在负环模板

int n;		//总点数
int h[N],w[N],e[N],ne[N],idx;		//邻接表存储所有边
int dist[N],cnt[N];			//dist[x]存储1号点到x号点的最短距离,cnt[x]存储1到x的最短路中经过的点数
bool st[N];			//存储每个点是否在队列中

//如果存在负环,则返回true,否则返回false
bool spfa()
{
    //不需要初始化dist数组
    //原理:如果某条最短路径上有n个点(除了自己),那么加上自己之后一共有n+1个点,由鸽巢原理一定有两个点相同,所以存在环
    
    queue<int>q;
    for(int i=1;i<=n;i++;i++)
    {
        q.push(i);
        st[i]=true;
    }
    
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n)return true;
                //如果从1号点到x的最短路中包含至少n个点(不包括自己),则说明存在环
                
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    
    return false;
}

---

Floyd算法

Floyd算法基本思想

邻接矩阵 d[i, j] 存储每一条边

初始化三重循环\(\quad\)for(int k = 1 ; k <= n ; k++ )

​\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)for(int i = 1 ; i <= n ; i++ )

\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)for(int j = 1 ; j <= n ; j++ )

​\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)\(\quad\)d[i, j] = min(d[i, j] , d[i, k] + d[k, j])

//Floyd算法模板

//初始化
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(i==j)d[i][j]=0;
		else d[i][j]=0x3f3f3f3f;

//算法结束后,d[a][b]表示a到b的最短距离
void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

标签：存储,dist,int,短路,问题,算法,quad,号点
From： https://www.cnblogs.com/evilboy/p/17359555.html