Shortest Path   2011-10-27


shortest path : dijstra 、 Bellman 、 Floyd 、 SPFA

1. dijstra

int data[M][M]; // init INF
int lowc[M];
int vis[M];
int n, m;
void djst(int p) {
int i, j;
for(i = 1; i <= n; i++) {
vis[i] = 0;
lowc[i] = data[p][i];
}
vis[p] = 1;
for(i = 1; i <= n-1; i++) {
int minc = INF, c = 0, lk;
for(j = 1; j <= n; j++) {
if(vis[j] == 0 && lowc[j] < minc) {
minc = lowc[j];
c = j;
}
}
if(c == 1) break;
vis[c] = 1;
for(j = 1; j <= n; j++) {
if(vis[j] == 0 && data[c][j] + minc > 0 && data[c][j] + minc < lowc[j]) {
lowc[j] = data[c][j] + minc;
}
}
}
cout << lowc[1] << endl;
}

2. Bellman

#define INF ((long long)(1))<<62
#define N 301
using namespace std;
struct edge{
int u;
int v;
long long w; // 注意
}e[N*N];
int m, n;
long long d[1005];
bool bellman_ford(int s, int di) {
int i, j;
for(i = 1; i < n; i++) {
d[i] = INF;
}
d[s] = 0;
for(i = 1; i <= n-1; i++) {
for(j = 1; j <= m; j++) {
if(d[e[j].u] != INF && d[e[j].u]+e[j].w < d[e[j].v]) // 对边进行操作 、松弛
d[e[j].v] = d[e[j].u] + e[j].w;
}
}
for(j = 1; j <= m; j++) {
if(d[e[j].u] != INF && (d[e[j].v] > d[e[j].u]+e[j].w)) // 很理解
d[e[j].v] = -INF;
}
if(d[di] == INF || d[di] == -INF) return false;
return true;
}

3. Floyd

4. SPFA

const int INF = 0x7fffffff;
const int N = 5501;
struct edge {
int to;
int w;
};
vector<edge> p[N]; // vector 实现邻接表
int d[N];
bool inque[N]; // 记录顶点是否在队列中,SPFA算法可以入队列多次
int cnt[N]; // 记录顶点入队的次数
int n, m, q;
bool SPFA(int s) {
queue<int> Q;
while(!Q.empty()) Q.pop();
int i;
for(i = 0; i <= n; i++) {
d[i] = INF;
}
d[s] = 0; // 源点的距离为 0
memset(inque, 0, sizeof(inque));
memset(cnt, 0, sizeof(cnt));
Q.push(s);
inque[s] = true;
cnt[s]++; // 源点入队列的次数增加
while(!Q.empty()) {
int t = Q.front();
Q.pop();
inque[t] = false;
for(i = 0; i < p[t].size(); i++) {
int to = p[t][i].to;
if(d[t] < INF && d[to] > d[t] + p[t][i].w) {
d[to] = d[t] + p[t][i].w;
cnt[to]++;
if(cnt[to] >= n) { //当一个点入队的次数>=n时就证明出现了负环
return false;
}
if(!inque[to]) {
Q.push(to);
inque[to] = true;
}
}
}
}
return true;
}

分享到:


  如果您觉得这篇文章对您的学习很有帮助, 请您也分享它, 让它能再次帮助到更多的需要学习的人. 您的支持将鼓励我继续创作 !
本文基于署名4.0国际许可协议发布,转载请保留本文署名和文章链接。 如您有任何授权方面的协商,请邮件联系我。

Contents

  1. 1. dijstra
  2. 2. Bellman
  3. 3. Floyd
  4. 4. SPFA