首页 > 代码库 > 最短路问题

最短路问题

2024-07-30 16:53:21   219人阅读

Bellman-Ford算法：（单源最短路）

从起点s出发到顶点i的最短距离d[i]
d[i] = min{d[j]+(从j到i的边的权值|)}
d[s] = 0;d[i] = INF; 依次更新最短路径。
实现：
const int MAX = 100;
const int INF = 1<<30;
struct edge{
    int from,to,cost;
};
edge es[MAX];
int n;
int d[MAX];
int V,E;
void slove(int s){
  fill(d,d+V,INF);
  d[s] = 0;
  while(true){
    bool update = false;
    for(int i=0;i<E;i++){
        edge e = es[i];
        if(d[e.from]!=INF && d[e.to]>d[e.from]+e.cost){
            d[e.to] = d[e.from] +e.cost;
            update = true;
        }
    }
    if(!update) break;
  }
}
//判断是否存在着负环
bool negative_loop(){
    memset(d,0,sizeof(d));
    for(int i=0;i<V;i++){
        for(int j=0;j<E;j++){
            edge e = es[j];
            if(d[e.to]>d[e.from]+e.cost){
                d[e.to] = d[e.from] +e.cost;

                //如果最后一次仍然更新 说明存在着负数的权值
                if(i==V-1) return true;
            }
        }
    }
    return false;
}

Dijkstra算法:

前提条件：不存在负环。
(1) 找到最短距离已经确定的点，从这个点出发更新相邻顶点的最短距离
(2)之后就不用需要关心（1）中已经确定的点了
图解：

算法过程：

a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。

b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。


const int MAX =100 ;
const int INF = 1<<30;
int cost[MAX][MAX];//cost[u][v] 表示e=（u,v）的权值
int d[MAX];
bool used[MAX];//顶点是否已经确定
int V;
void dijkstra(int s){
    fill(d,d+V;INF);
    fill(used,used+V,false);
    d[s]  = 0;
    while(true){
        int v = -1;
        for(int u=0;u<V;u++){
            if(!used[u] && (v==-1 || d[u]<d[v])) v = u;
        }
        if(v==-1) break;
        used[v] = true;

        for(int u=0;i<V;i++){
            d[u] = min(d[u],d[v]+cost[v][u]);
        }
    }
}
需要优化的是数值的插入和取出最小值的操作，所以使用堆结构，所以使用STL里面的优先队列正好。

代码：

struct edge{int from ,to,cost};
 const int MAX =100 ;
 const int INF = 1<<30;
 typedef pair<int,int> P;//first 最短距离,second 编号
 int V;
 vector<int> G[MAX];
 int d[MAX];
 void dijkstra(int s){
    fill(d,d+V;INF);
    d[s] = 0;
    priority_queue<P, vecotr<P>, greater<P> > que;
    que.push(P(0,s);
    while(!qie.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        if(d[v]<p.first){
            continue;
        }
        for(int i=0;i<G[v].size();i++){
            egde e = G[v][i];
            if(d[e.to]>d[e.from]+cost){
                d[e.to] = d[e.from]+cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
 }

Floyd-Warshall算法：

任意两点（i，j）之间的最短路 DP解决：
任一两点之间的距离 取决于是否经过k点：
(1) 不经过K点：
d[k][i][j] = d[k-1][i][j];
(2) 经过K点
d[k][i][k] = d[k-1][i][k]+d[k-1][k][j]
所以:
d[k][i][j] = min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j]);
使用一个DP数组：
dp[i][k] = min(dp[i][j],dp[i][k]+dp[k][j]);
实现：
int dp[MAX][MAX];
int V;
void warshall_floyd(){
    for(int k=0;k<V;k++)
        for(int i = 0;i<V;i++)
            for(int j=0;j<v;j++)
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]);
}




                      

最短路问题


联系
我们