dijkstra最短路径例题（用dijkstra算法求a到f的最短路径）

本文目录

• 用dijkstra算法求a到f的最短路径
• 用C++求dijkstra算法求最短路径
• 运筹学用dijkstra算法求最短路径
• 用迪杰斯特拉算法计算最短路径
• 利用Dijkstra算法,求下图从1出发到其余各点的最短路径.
• 谁能举一个Pascal中Dijkstra算法求单源最短路径问题的例子并作一些说明
• 利用Dijkstra算法求下图中从顶点1到其它各顶点间的最短路径，按下面表格形式

用dijkstra算法求a到f的最短路径

#include 《stdio.h》  
int a;  //记录邻接矩阵  
int dist;    //到每个点的最短路  
int m,n;        //m条路，n个点  
const int INF=0xfffffff;  
void init()                 //初始化数据  
{  
    for(int i=0;i《n;i++)  
        for(int j=0;j《n;j++)  
            a[i][j]=(i==j?0:INF);  
}  
  
void dijkstra(int u)    //从第u个点开始走  
{  
    int sign={0};  //标记走过否  
    int x=u;  
    int i,j;  
    for(i=0;i《n;i++)     //初始化到各点距离  
        dist[i]=a[x][i];  
    dist[x]=0;          //到本身距离为0  
    sign[x]=1;          //改点以走过  
    for(i=1;i《=n-2;i++)                
    {  
        int min=INF;  
        for(j=0;j《n;j++) //在为走过的点中取距离x最短的点  
        {  
        if(!sign[j] && min》dist[j])  
        {  
            min=dist[j];  
            x=j;  
        }  
        }  
        sign[x]=1;      //标记，已走过  
  
        for(j=0;j《n;j++)//x以改变，更新dist值  
        {  
          if(!sign[j] && dist[x]+a[x][j]《dist[j] && a[x][j]《INF)  
               dist[j]=a[x][j]+dist[x];  
        }  
    }  
}  
int main()  
{  
    int i;  
    while(scanf(“%d %d“,&n,&m)!=EOF)  
    {  
        init();  
        for(i=0;i《m;i++)  
        {  
            int x,y,z;  
            scanf(“%d %d %d“,&x,&y,&z);  
            if(z《a[x][y])        //取两点多条路最小路  
                a[x][y]=z;  
            if(z《a[y][x])  
                a[y][x]=z;  
        }  
        int s,t;  
        scanf(“%d %d“,&s,&t);     
        dijkstra(s);  
          
        if(dist[t]《2000000)  
            printf(“%d\n“,dist[t]);  
        else  
            printf(“-1\n“);  
    }  
    return 0;  
}

参考链接 ：http://blog.csdn.net/ouyangying123/article/details/38706957

用C++求dijkstra算法求最短路径

/**************************************************************
* 给定一个带权有向图G = (V，E)，其中每条边的权是一个非负整数。*
* 另外还给定V中的一个顶点，称为源。现在我们要计算从源到所有其 *
* 他各顶点的最短路长度。这里路径长度是路上各边权之和。这个问 *
* 题通常称为单源最短路径问题。 *
***************************************************************/
#include《iostream.h》

#define INFINITE 100

void main()
{
int j,i,n,k,t,**w,*s,*p,*d;

cout《《“input the value of n:“;
cin》》n;
cout《《endl;

d = new int[n];
s = new int[n];
p = new int[n];
w = new int*[n];

for(i = 0; i 《 n; i++)
{
w[i] = new int[n];
}

for(i = 0; i 《 n; i++)
for(j = 0; j 《 n; j++)
cin》》w[i][j];

for(s = 1,i = 1; i 《 n; i++)
{
s[i] = 0;
d[i] = w[i];
if(d[i] 《 INFINITE)
p[i]=0;
else
p[i]=-1;
}

for(i = 1; i 《 n; i++)
{
t = INFINITE;
k = 1;
for(j = 1; j 《 n; j++)
if((!s[j]) && (d[j] 《 t))
{
t = d[j];
k = j;
}
s[k]=1;//point k join the S
for (j = 1; j 《 n; j++)
if((!s[j]) && (d[j] 》 d[k] + w[k][j]))
{
d[j] = d[k] + w[k][j];
p[j] = k;
}

}
cout《《“从源点到其它顶点的最短距离依次如下：“;
for(i=1;i《n;i++) cout《《d[i]《《“ “;
cout《《endl;

}
/*********
顶点个数用n表示，这里给出的例子n=6
100 1 12 100 100 100
100 100 9 3 100 100
100 100 100 100 5 100
100 100 4 100 13 15
100 100 100 100 100 4
100 100 100 100 100 100
具体例子见 电子工业出版社 《算法设计技巧与分析》148页
************/

运筹学用dijkstra算法求最短路径

就是通过广度搜索遍历当前节点和子节点的关系，然后再依次递归。
我给你开个头啊:
首先设首节点为1,那么子节点是2,3,4,那么我分别遍历
1-2 = 4
1-3 = 5
1-4 = 2
全部遍历完后我在从下面的第一个子节点开始遍历,
1(-2)-5 = 11
1(-2)-3 = 10 和1-3 = 5 对比 5《10 那么 1-3 = 5

1(-3)-2 = 11 和1-2 = 4进行对比 4《11 那么1-2 = 4
1(-3)-6 = 14
1(-3)-4 = 6 和 1-4 = 2进行对比 2《 6 那么 1-4 =2

1(-4)-3 = 3 和 1-3=5 进行对比 5 》 3 那么 1-3 = 3
.......................
依次遍历完整个图

最开始设1 到其他点的路径为无限大，
然后依次遍历，if( ( 1到当前点的路径 + 当前点到某子节点的路径) 《 (1 到该子节点的路径) )
1到该子节点的路径 = 1到当前点的路径 + 当前点到该子节点的路径)

用迪杰斯特拉算法计算最短路径

给定一个有向图，求v1到其他各节点的最短路径长度，以及最短路径。

要求：对dijkstra算法进行补充，使新算法在找出这些最短路径长度的同时，也能求出路径上的节点序列。

输入：一个有向带权图

这里写图片描述

输出的基本形式如下：

这里写图片描述

利用Dijkstra算法,求下图从1出发到其余各点的最短路径.

MVC方法常用于构建用户界面在Smalltalk。通过MVC设计模式隐藏在可以帮助你了解我们所说的“模范”的意思。

MVC包括三种类型的对象，模型是应用程序对象，查看其屏幕表示，控制器定义了处理用户输入（响应）模式。在MVC方式之前，应用程序，通常是三个对象组合在一起，这些功能结合在一起，将它们分开MVC应用程序，旨在提供灵活性和可重用性。

MVC通过创建订阅/通知视图和模型，视图和模型对象之间的分离协议。视图对象必须确保它反映了状态模型表示对象，当数据模型对象的变化，模型对象的通知（通知）视图对象，作为反应，这种行为，每有一个视图对象进行更新的机会。这种方法使得有可能对多个视图的对象模型中的对象提供不同的表示形式。您还可以创建一个新的视图对象模型对象，而不是重新写模式。下图显示了一个模型和三视图：点击看详细从表面上看，这个例子反映的视图和模型设计的分离。然而，这是专为一类的更一般的问题：降低了莲和性的目的，这样，当一个对象改变时，也不会影响到其它的目的，甚至不需要知道另一个对象的实现细节。这更普遍的模式将在Observer模式描述。另一个特点是方式

MVC，视图对象是可嵌套定义。例如，通过嵌套对象视图对象按钮控制面板按钮视图包含复杂的实施;对象观众嵌套的用户界面视图的对象可以被重新使用的调试器组件。使用CompositeView类（查看子类），以支持嵌套图，其行为和查看对象，可用于任何场合视图对象可以使用的行为一致MVC方法。

因此，我们可以把复合视图这样的一种方式来解决它的设计（时尚）的一个组成部分。同样，这样的设计可以抽象另一个更普遍的问题（解决方案）：在某些情况下，我们进入的对象群体，并视为一组处理单个对象。通过这种方式，我们用它来形容复合设计模式。它可以让你建立一流的水平，在这个水平上，某些子类定义基本对象（如按钮），而其他类可以定义合成对象（CompositeView），合成对象可以组装成更复杂的对象原始对象。

同样，MVC也可以改变视图类（视图）的方式，用户的反应，不改变其视觉表现。你可能想改变其响应于键盘，如使用弹出菜单，而不是命令键的方式。 MVC封装的响应机制，该对象（控制器）的控制。控制器具有一个类层次结构，并且容易从现有的控制器来实现建立一个变种 - 一个新的控制器。

视图（View），通过对象（实例）控制器对象的实例，以实现特定的应对策略。为了实现不同的政策，可以简单地使用不同的控制器实例来替换当前实例。即使在运行时改变控制器的视图来改变响应于用户输入（策略）的对象图。例如，一个浏览对象可以被设置为关闭状态，即，在没有任何用户输入的响应。为了实现这一目标，就干脆让控制器忽略所有输入事件。这

视图 - 控制器关系，这是策略设计模式的一个典型例子。所谓策略，这样一种对象，它表示的算法。当你要替换算法（无论是静态还是动态替换替换），这是特别有用，这样的算法可能有很多变数，或有复杂的数据结构。

MVC中也使用其他的设计模式，例如，使用工厂方法模式来描述默认控制器类图;使用装饰图案添加滚动条，以查看等。但在MVC的方式主要是上述观察，综合和战略设计模式。

谁能举一个Pascal中Dijkstra算法求单源最短路径问题的例子并作一些说明

[问题分析]
对于一个含有n个顶点和e条边的图来说，从某一个顶点Vi到其余任一顶点Vj的最短路径，可能是它们之间的边（Vi，Vj），也可能是经过k个中间顶点和k+1条边所形成的路径(1≤k≤n-2)。下面给出解决这个问题的Dijkstra算法思想。
设图G用邻接矩阵的方式存储在GA中，GA[i,j]=maxint表示Vi，Vj是不关联的，否则为权值（大于0的实数）。设集合S用来保存已求得最短路径的终点序号，初始时S=[Vi]表示只有源点，以后每求出一个终点Vj，就把它加入到集合中并作为新考虑的中间顶点。设数组dist[1..n]用来存储当前求得的最短路径，初始时Vi，Vj如果是关联的，则dist[j]等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，dist[j]可能越来越小。再设一个与dist对应的数组path[1..n]用来存放当前最短路径的边，初始时为Vi到Vj的边，如果不存在边则为空。
执行时，先从S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为dist[m]），该元素值就是从源点Vi到终点Vm的最短路径长度，对应的path[m]中的顶点或边的序列即为最短路径。接着把Vm并入集合S中，然后以Vm作为新考虑的中间顶点，对S以外的每个顶点Vj，比较dist[m]+GA[m,j]的dist[j]的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替dist[j]，同时把Vj或边（Vm，Vj）并入到path[j]中。重复以上过程n-2次，即可在dist数组中得到从源点到其余各终点的最段路径长度，对应的path数组中保存着相应的最段路径。

下面给出具体的Dijkstra算法框架（注：为了实现上的方便，用一个一维数组s[1..n]代替集合S，用来保存已求得最短路径的终点集合，即如果s[j]=0表示顶点Vj不在集合中，反之，s[j]=1表示顶点Vj已在集合中）。
Procedure Dijkstra(GA,dist,path,i)；
{表示求Vi到图G中其余顶点的最短路径，GA为图G的邻接矩阵，dist和path为变量型参数，
其中path的基类型为集合}
Begin
For j:=1 To n Do Begin {初始化}
If j《》i Then s[j]:=0 Else s[j]:=1；
dist[j]:=GA[i,j]；
If dist[j]《maxint Then path[j]:=[i]+[j] Else path[j]:=[ ]；
End；
For k:=1 To n-2 Do
Begin
w:=maxint；m:=i；
For j:=1 To n Do {求出第k个终点Vm}
If (s[j]=0) and (dist[j]《w) Then Begin m:=j；w:=dist[j]； End；
If m《》i Then s[m]:=1 else exit；
{若条件成立，则把Vm加入到S中，
否则退出循环，因为剩余的终点，其最短路径长度均为maxint，无需再计算下去}
For j:=1 To n Do {对s[j]=0的更优元素作必要修改}
If (s[j]=0) and (dist[m]+GA[m,j]《dist[j])
Then Begin Dist[j]:=dist[m]+GA[m,j]；path[j]:=path[m]+[j]；End；
End；
End；

（1）从一个顶点到其余各顶点的最短路径
对于一个含有n个顶点和e条边的图来说，从某个顶点vi到其余任一顶点vj的最短路径，可能是它们之间的边（vi，vj），也可能是经过k个中间点和k+1条边所形成的路径（1≤k ≤n-2）。
首先来分析Dijkstra的算法思想
设图G用邻接矩阵的方式存储在GA中，GA[I，j]=maxint表示vi，vj是不关联的，否则为权值（大于0的实数）。设集合S用来存储保存已求得最短路径的终点序号，初始时S=[vi]表示只有源点，以后每求出一个终点vj，就把它加入到集合中并作为新考虑的中间顶点。设数组dist[1..n]用来存储当前求得的最短路径，初始时vi，vj如果是关联的，则dist[j]等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，dist[j]可能越来越小。再设一个与dist对应的数组path[1..n]用来存放当前最短路径的边，初始时vi到vj的边，如果不存在边则为空。
执行时，先从S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为dist[m]），该元素值就是从源点vi到终点vm的最短路径长度，对应的path[m]中的顶点或边的序列即为最短路径。接着把vm并入集合S中，然后以vm作为新考虑的中间顶点，对S以外的每个顶点vj，比较dist[m]+GA[i，j]与dist[j]的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替dist[j]，同时把vj或边（vm，vj）并入到path[j]中。重复以上过程n-2次，即可在dist数组中得到从源点到其余个终点的最短路径长度，对应的path数组中保存着相应的最短路径。
为了实现上的方便，用一个一维数组s[1..n]代替集合s，用来保存已求得最短路径的终点集合，即如果s[j]=0表示顶点vj不在集合中，反之，s[j]表示顶点vj已在集合中）。

Procedure dijkstra (GA,dist path,I)
begin
for j:= 1 to n do begin
if j《》I then s[j]:=0;{j不在集合中} else s[j]:=1;{j在集合中}；
dist[j]:=GA[I,J];
IF dist [j]《maxint {maxint为假设的一个足够大的数}
Then path [j]:=[I]+[j]
Else path[j]:=[ ];
End;
For k:= 1 to n-1 do begin w:=maxint;m:=I;
For j:= 1 to n do{求出第k个终点Vm}
if (s[j]=0)and(dist[j]《w) then begin m:=j;w:=dist[j];end;
If m《》I then s[m]:=1 else exit;{若条件成立，则把Vm加入到s中，否则退出循环，因为
剩余的终点，其最短路径长度均为maxint，无需再计算下去}
for j:=1 to n do {对s[j]=0的更优元素作必要修改}
if (s[j]=0)and (dist[m]+GA[m,j]《dist[j])
then begin
dist[j]:=dist[m]+GA[m,j];
path[j]:=path[m]+[j];
End;
End;
End;

用集合的思想：

for k:=1 to n-1 do
begin
wm:=max;j:=0;
for i:=1 to n do
if not(i in s)and(dist[i]《wm) then begin j:=i;wm:=dist[i];end;
s:=s+[j];
for i:=1 to n do
if not(i in s)and(dist[j]+cost[j,i]《dist[i]) then
begin dist[i]:=dist[j]+cost[j,i];path[i]:=path[j]+char(48+i);end;
end;

利用Dijkstra算法求下图中从顶点1到其它各顶点间的最短路径，按下面表格形式

v1到v2：10为最短路径；

v1到v3：7为最短路径；

v1到v4：8为最短路径；

v1到v5：v1-》 v2 -》 v5 =10+6= 16；v1v3v5=7+9=16;v1v4v6v5=8+5+2=15; 15为最短路径；

v1到v6：v1v2v3v6=10+2+9=21；v1v3v6=7+9=16；v1v4v6=8+5=13；13为最短路径；

v1到v7：v1v2v5v7=10+6+20=36；v1v3v5v7=7+9+20=36；v1v3v6v7=7+9+30=46；

v1v4v6v7=8+5+30=42；v1v4v6v5v7=35；35为最短路径

Dijkstra：

求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）。源点可达的话，O（V*lgV+E*lgV）=》O（E*lgV）。当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2）。若是斐波那契堆作优先队列的话，算法时间复杂度，则为O（V*lgV + E）。

以上内容参考：百度百科-最短路径算法