Dijkstra算法求单源最短路径

Dijkstra's 最短路径算法能不能解这个含有负权重的问题~

Dijkstra算法当中将节点分为已求得最短路径的集合（记为S）和未确定最短路径的个集合（记为U），归入S集合的节点的最短路径及其长度不再变更，如果边上的权值允许为负值，那么有可能出现当与S内某点（记为a）以负边相连的点（记为b）确定其最短路径时，它的最短路径长度加上这条负边的权值结果小于a原先确定的最短路径长度，而此时a在Dijkstra算法下是无法更新的，由此便可能得不到正确的结果。求带负权值边的单源最短路径可以用贝尔曼-福特算法。

将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止。具体步骤1、选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径（确定数据结构：因为求的是最短路径，所以①就要用一个记录从源点v到其它各顶点的路径长度数组dist[],开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。②设一个用来记录从源点到其它顶点的路径数组path[],path中存放路径上第i个顶点的前驱顶点）。2、在上述的最短路径dist[]中选一条最短的，并将其终点（即）k加入到集合s中。3、调整T中各顶点到源点v的最短路径。 因为当顶点k加入到集合s中后，源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。调整方法是比较dist[k]+g[k,j]与dist[j]，取其中的较小者。4、再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点。 SPFA实际上是Bellman-Ford基础上的队列优化SPFA(G,w,s)1. INITIALIZE-SINGLE-SOURCE(G,s)2. INITIALIZE-QUEUE(Q)3. ENQUEUE(Q,s)4. While Not EMPTY(Q)5. Do udq;inti,j,x,to;for(i=1;idist[x]+adjmap[x][i].weight)){dist[to]=dist[x]+adjmap[x][i].weight;path[to]=x;if(!in_queue[to]){in_queue[to]=true;in_sum[to]++;if(in_sum[to]==nodesum)return false;if(!dq.empty()){if(dist[to]>dist[dq.front()])dq.push_back(to);elsedq.push_front(to);}elsedq.push_back(to);}}}}returntrue;}

分给我，这是模板，很好用，我做acm用的

#define MAX 110
#define MAXVALUE 1000

int Cost[MAX][MAX],Dist[MAX];

void Dijkstra(int n,int v,int *Dist) //或 int Dist[MAX];
{
int newdist,i,j,temp,u;
bool s[MAX];

for(i=0;i<n;i++)
{
Dist[i]=Cost[v][i];
s[i]=false;
}

Dist[v]=0;
s[v]=true;

for(i=1;i<n;i++)
{
temp=MAXVALUE;
//u=v;
for(j=0;j<n;j++)
{
if((!s[j]) && (Dist[j]<temp))
{
u=j; temp=Dist[j];
}
}
s[u]=true;
for(j=0;j<n;j++)
{
if((!s[j]))// && (Cost[u][j]<MAXVALUE))
{
newdist=Dist[u]+Cost[u][j];
if(newdist<Dist[j]) Dist[j]=newdist;

}
}
}
return ;
}

program dijkstra;
const
inf = '';
outf = '';
maxn = 100;

var
n, s, t: longint;
judge: array[1..maxn] of boolean;
dis: array[1..maxn] of longint;
a: array[1..maxn, 1..maxn] of longint;

procedure assignfile;
begin
assign(input, inf); reset(input);
assign(output, outf); rewrite(output);
end;

procedure closefile;
begin
close(input); close(output);
end;

procedure init;
var
i, j: longint;
begin
readln(n);
for i := 1 to n do begin
for j := 1 to n do read(a[i, j]);
readln;
end;
readln(s, t);
end;

procedure process;
var
now, i: longint;
begin
fillchar(dis, sizeof(dis), 255); dis[s] := 0;
fillchar(judge, sizeof(judge), true);
now := s;
repeat
judge[now] := false;
for i := 1 to n do if a[now, i] > 0 then
if (dis[now] + a[now, i] < dis[i]) or (dis[i] < 0) then
dis[i] := dis[now] + a[now, i];
now := s;
for i := 1 to n do if (dis[i] > 0) and (judge[i]) then
if (dis[i] < dis[now]) or (now = s) then now := i;
until (now = t) or (now = s);
end;

procedure print;
begin
writeln(dis[t]);
end;

begin
assignfile;
init;
process;
print;
closefile;
end.

怎么了?

---

元谋县13868972841： 用dijkstra算法计算源点到个结点的最短路径....谢谢亲爱的朋友~ 详细答案 - ？
笪志复方： (这里描述的是从节点1开始到各点的dijkstra算法,其中Wa->b表示a->b的边的权值,d(i)即为最短路径值) 1. 置集合S={2,3,...n}, 数组d(1)=0, d(i)=W1->i(1,i之间存在边) or +无穷大(1.i之间不存在边) 2. 在S中,令d(j)=min{d(i),i属于S},令S=S-{j},若S为空集则算法结束,否则转3 3. 对全部i属于S,如果存在边j->i,那么置d(i)=min{d(i), d(j)+Wj->i},转2

元谋县13868972841： Dijkstra算法求单源最短路径 - ？
笪志复方： 分给我,这是模板,很好用,我做acm用的#define MAX 110 #define MAXVALUE 1000int Cost[MAX][MAX],Dist[MAX];void Dijkstra(int n,int v,int *Dist) //或 int Dist[MAX]; {int newdist,i,j,temp,u;bool s[MAX]; for(i=0;i<n;i++){Dist[i]=Cost[v][i]; ...

元谋县13868972841： 怎么用c语言实现单源最短路径问题?要求是用Dijkstra算法,最好写出所有的代码 ,包括结构定义等等,对一 - ？
笪志复方： C语言代码://清华大学出版社光盘的代码 void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D) { // 算法7.15// 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]// 及其带权长度D[v].// 若P[v][w]为TRUE,则w...

元谋县13868972841： 谁能举一个Pascal中Dijkstra算法求单源最短路径问题的例子并作一些说明 - ？
笪志复方： 解释一下吧 举一个简单的例子 设图 G(V,E) (V是顶点集合,E是边集合) 顶点1 ---2--- 顶点2 ---3--- 顶点3 (无向图,关于无向图这一点,不理解也不影响) 这个时候 邻接矩阵0 2 ∞2 0 3 ∞ 3 0 (∞ 表示无连接;0表示该边连接了两个相同的顶点,是不...

元谋县13868972841： 求单源点最短路径的Dijkstra法是按的顺序,求源点到各顶点的最短路径...？
笪志复方： Dijkstra算法的适用范围是权值非负的图,即解决带有非负权值的图中的单源最短路径问题 比方说你从甲地走到乙地 需要走的步数怎么会是负值呢 是吧

元谋县13868972841： 怎样用DIJKSTRA算法设计最短路径? - ？
笪志复方： 以下................输入时,将s,t,x,y,z五个点按照1,2,3,4,5起别名,输入格式按照下图例所示 当提示Please enter the vertex where Dijkstra algorithm starts:时输入算法的起始点 比如计算结果v1v4v2表示从点1到点2经过1,4,2为最短路径 Dijkstra算法的...

元谋县13868972841： 最短路径算法 Dijkstra 用C语言编出来？
笪志复方： Dijkstra算法--c++源代码--by 伟伟猪 [转贴 2005-12-15 20:21:00 ] 发表者: 伟伟猪 /*********************************************** 设G=(V,E)是一个每条边都有非负长度的有向图,有一个特异的顶点s称为缘. 单源最短路径问题,或者称为最短路径问题...

元谋县13868972841： 求Dijkstra算法,计算网络最短路径希望有详细说明,有典型例题 - ？
笪志复方：[答案] 算法导论上有比较清晰的讲解