最短路问题

Dijkstra算法

说到最短路问题，我相信只要是学习过计算机的人都有听说过Dijkstra他老人家，他对程序的贡献远不止一个算法。

1 提出“goto有害论”;

2 提出信号量和PV原语;

3 解决了“哲学家聚餐”问题;

4 最短路径算法(SPF)和银行家算法的创造者;

5 第一个Algol 60编译器的设计者和实现者;

6 THE操作系统的设计者和开发者;

按照他自己的称呼，他是一个程序员。不得不说，这样的程序员实在是太伟大了。

让我们回到Dijkstra算法上。

这个算法的核心是维护d[i]=>i号结点和起点s距离的估值，之所以是估值，是因为它可能并不是真的最短值。要经历一个过程，才能够成为真正的最短值。

这次我们先看算法好了。

清除所有点的标号(所有点都是未知的)设d[0]=0,d[i]=INF（无限大）循环n次{    #在未知的点中，寻找出d值最小的结点x    *标记x为已知    对于从x出发的所有边（x,y）更新 d[y]=min(d[y],d[x]+w[x][y])   }

我们看到了这个过程（标了*号的这一行）。

是当d[x]为当前所有未知点中的最小值时，别的所有的到达x的走法都是绕远路、舍近求远。所以，这时我们可以确定 d[x]就是x点和起点s的最短距离！

我们来写一个简单的版本好了

//v 标记是否已知//memset(v,0,sizeof(v));for(int i=0;i

代码中带有注释的两处其实都可以优化。

查找最小结点这种工作其实对于一个优先队列来说非常合适。

这个队列中拥有d值以及其对应的结点号（d[i]和i）

还需要定义>操作符

struct HeapNode{    int d,i;    bool operator < (const HeapNode& rhs) const{        return d>rhs.d;     } }

在正式完成算法之前，我们首先对数据结构进行些许该进。另一个可以优化的地方也在这里，将w[i][j]这样一个N^2的数组转换为一个vector< int> Gi[maxn]来存储边号，用vector< Edge> Edges来存储边。

struct Edge{    int from,to;    int dist;    Edge(int x,int y,int d):from(u),to(v),dist(d){}}

struct Dijstra{    vector
     
       G[maxn];    vector
      
        edges;    int m,n;    int d[mniaxn],v[maxn];    int p[maxn];/*保存父结点*/    void init(int n){        this->n=n;        for(auto item:G)item.clear();        edges.clear();    }    void AddEdge(int from,int to,int dist){        edges.push_back(Edge(from,to,dist));        m=edges.size();        G[from].push_back(m-1);/*m-1刚好为这个边在edges中的索引*/    }    void dijkstra(int s){    ...    }}
      
     

主算法：

void Dijkstra(int s){    priority_queue
     
       Q;    for(int i=0;i
      
       d[u]+e.dist){             d[e.to]=d[u]+e.dist;             p[e.to]=G[u][i];             Q.push((HeapNode){d[e.to],e.to})            }        }    }}
      
     

是不是有点累了呢。没关系，只要看懂了第一段代码，对Dijkstra的贪心思想熟记于心就可以了！

但是Dijkstra算法在面对有负权边时就无能为力了，有负环的话就意味着最短路径不存在！

这个时候我们需要另一种算法Bellman-Ford算法

Bellman-Ford

我们先直接上代码看看

for(int i=0;i

需要指出的是：Bellman-Ford算法非常低，其优化这里先不给出

我们应该关注的重点在于Floyd算法：

for(int k=0;k

Floyd求出的是各个点对的距离。

版权声明：本文为博主原创文章，转载请标明出处。