狄克斯特拉算法图解

Ⅰ 大学作业帮 一般线性规划 求详细解答步骤

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

#include<stdio.h>
#include<stdlib.h>
#define max 11000000000
inta[1000][1000];
intd[1000];//d表示某特定边距离
intp[1000];//p表示永久边距离
inti,j,k;
intm;//m代表边数
intn;//n代表点数
intmain()
{
scanf("%d%d",&n,&m);
intmin1;
intx,y,z;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
a[x][y]=z;
a[y][x]=z;
}
for(i=1;i<=n;i++)
d[i]=max1;
d[1]=0;
for(i=1;i<=n;i++)
{
min1=max1;
for(j=1;j<=n;j++)
if(!p[j]&&d[j]<min1)
{
min1=d[j];
k=j;
}
p[k]=j;
for(j=1;j<=n;j++)
if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j])
d[j]=d[k]+a[k][j];
}
for(i=1;i<n;i++)
printf("%d->",p[i]);
printf("%d\n",p[n]);
return0;
}

Ⅱ 狄克斯特拉的介绍

狄克斯特拉1930年5月11日生于荷兰鹿特丹的一个知识分子家庭，在兄弟姊妹4人中排行第三。他的父亲是一名化学家和发明家，曾担任荷兰化学会主席。他母亲则是一位数学家。他成功地设计并实现了在有障碍物的两个地点之间找出一条最短路径的高效算法，这个算法被命名为“狄克斯特拉算法”，解决了机器人学中的一个十分关键的问题，即运动路径规划问题，至今仍被广泛应用，被认为是利用“贪心法”(greedy method)设计算法的一个成功范例。

Ⅲ 狄克斯特拉的人生成就

狄克斯特拉1930年5月11日生于荷兰鹿特丹的一个知识分子家庭，在兄弟姊妹4人中排行第三。他的父亲是一名化学家和发明家，曾担任荷兰化学会主席。他母亲则是一位数学家。
狄克斯特拉的少年时代是在德国法西斯占领军的铁蹄下度过的。由于食物短缺，他被送到乡下他父亲的一个朋友那里去。纳粹德国投降后，1945年7月，十分虚弱的狄克斯特拉才和家人重新团聚。狄克斯特拉原打算学法律，毕业后到联合国工作，为维护世界和平服务。但他中学毕业时，数理化成绩都特别好，因此他父亲说服了他，1948年进莱顿大学学习数学与物理。在学习理论物理的过程中，狄克斯特拉发现这个领域中的许多问题都需要进行大量复杂的计算，于是决定学习计算机编程。1951年，他自费赴英国参加了剑桥大学举办的一个程序设计培训班，学习在EDSAC(Electronic Delay Storage Automatic Calculator，这是由另一位首届计算机先驱奖获得者威尔克斯主持设计与开发的世界上第一台存储程序式电子计算机)上的编程方法，这使他成为世界上第一批程序员之一。第二年，阿姆斯特丹数学中心了解到这一情况，拟聘他为兼职程序员。狄克斯特拉开始时有些犹豫，因为世界上当时还没有“程序员”这一职业。数学中心的计算部主任、Algol语言的设计者之一、荷兰的计算技术先驱维京格尔藤(A．van Wijingaarden，1916—1987，因在设计Algol 68时，为解决上下文有关性这一难题而提出了一种具有很强描述能力的新的文法，称做二级文法又称W文法而闻名。他是1986年计算机先驱奖获得者之一，也曾对另一位首届计算机先驱奖获得者N．Wirth的研究产生过影响)对他说，目前程序设计虽然还没有成为学科，不被重视，但既然计算机已经有了，正处于开创阶段，你未来就有可能使程序设计成为一个受人尊敬的学科。这段话说动了狄克斯特拉，使他接受了这个职位，而且越干越有兴趣，这样，他在第二年就结束了在莱顿大学的学业，成为数学中心全日制的工作人员，从此进入计算机领域，并且正如维京格尔藤所预言的那样，逐渐成为该领域的知名专家，创造出了许许多多的“第一”。
1956年，他成功地设计并实现了在有障碍物的两个地点之间找出一条最短路径的高效算法，这个算法被命名为“狄克斯特拉算法”，解决了机器人学中的一个十分关键的问题，即运动路径规划问题，至今仍被广泛应用，被认为是利用“贪心法”(greedy method)设计算法的一个成功范例。
1959年，在数学中心将他们原先的ARMAC计算机进行升级的过程中，狄克斯特拉设计了一种处理程序，成功地解决了“实时中断”（real-time interrupt)问题。狄克斯特拉的博士论文就是以此为课题完成的，并在阿姆斯特丹大学通过论文答辩而获得博士学位。
1960年8月，Algol 60文本推出刚刚半年多，狄克斯特拉和他在数学中心的同事仲纳凡尔特(J．A．Zonneveld)一起就率先实现了世界上第一个Algol 60编译器，比欧美其他各国学者实现Algol 60早一年还多。这一成就引起各国计算机学者的惊叹，并因此奠定了狄克斯特拉作为世界一流计算机学者在科学界的地位。
1962年，狄克斯特拉离开数学中心进入位于荷兰南部的艾恩德大学(Eindhoven Technical University)任数学教授。在这里，X8计算机的开发，设计与实现了具有多道程序运行能力统——THE Multiprogramming System。THE是艾恩德霍芬技荷兰文Technische Hoogeschool Eindhoven的词头缩写。狄克THE这个系统中所提出的一系列方法和技术奠定了计算作系统的基础，尤其是关于多层体系结构、顺序进程之间的斥机制这样一些重要的思想和概念都是狄克斯特拉在THE中首先提出并为以后的操作系统如UNIX等所采用的。为了在单处理机的情况下确定进程(process)能否占有处理机，狄克斯特拉将每个进程分为“就绪”(ready)、“运行”(running)和“阻塞”(blocking)三个工作状态。由于在任一时刻最多只有一个进程可以使用处理机，正占用着处理机的进程称为“运行”进程。当某进程已具备了使用处理机的条件，而当前又没有处理机供其使用，则使该进程处于“就绪”状态，当运行进程由于某种原因无法继续运行下去时，就停止其占用处理机，使之进入“阻塞’’状态，待造成其退出运行的条件解除，再进入“就绪”状态。而对系统中所有同时运行的进程之间所存在的相互制约的同步(synchronization，指为了避免错误，在一个进程访问共享数据时，另一个进程不访问该数据)和互斥(mutually-exclusive，指两个进程不能同时在一个临界区中使用同一个可重复使用的资源，诸如读写缓冲区)两个关系，狄克斯特拉巧妙地利用火车运行控制系统中的“信号灯”(semaphore，或叫“信号量”)概念加以解决。所谓信号灯，实际上就是用来控制进程状态的一个代表某一资源的存储单元。例如，P1和P2是分别将数据送入缓冲B和从缓冲B读出数据的两个进程，为了防止这两个进程并发时产生错误，狄克斯特拉设计了一种同步机制叫PV操作”，P操作和V操作是执行时不被打断的两个操作系统原语。执行P操作P(S)时信号量S的值减1，若结果不为负则P(S)执行完毕，否则执行P操作的进程暂停以等待释放。执行V操作V(S)时，S的值加1，若结果不大于0则释放一个因执行P(S)而等待的进程。对P1和凹可定义两个信号量S1和S2，初值分别为1和0。进程P1在向缓冲B送人数据前执行P操作P(S1)，在送人数据后执行V操作V(S2)。进程P2在从缓冲B读取数据前先执行P操作P(S2)，在读出数据后执行V操作V(S1)。当P1往缓冲B送入一数据后信号量S1之值变为0，在该数据读出后S1之值才又变为1，因此在前驱数未读出前后续数不会送入，从而保证了P1和P2之间的同步。我国读者常常不明白这一同步机制为什么称做PV操作，原来这是狄克斯特拉用荷兰文定义的，因为在荷兰文中，通过叫passeren，释放叫，VRIJGEVEN，PV操作因此得名。这是在计算机术语中不用英语表达的极少数的例子之一。

Ⅳ dijkstra算法是什么

Dijkstra算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。

其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。

不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。

举例来说，如果图中的顶点表示城市，而边上的权重表示着城市间开车行经的距离。Dijkstra算法可以用来找到两个城市之间的最短路径。

Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。（u,v)表示从顶点u到v有路径相连。我们以E所有边的集合，而边的权重则由权重函数w: E→[0,∞］定义。

因此，w(u,v)就是从顶点u到顶点v的非负花费值（cost)。边的花费可以想象成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。

已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径（i.e.最短路径）。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。

Ⅳ c++数据结构的图的应用，求图的最小生成树和最短路径有什么不同，或者是普里姆算法和狄克斯特拉算法有

不知道你的手头有没有一本经典的书籍叫做《大话数据结构》，如果解释的话，似乎还真不容易解释，请找一下这本书的电子版，查阅一下相关章节更清楚，祝你好运。
http://yunpan.cn/cwbziapG5St3w 访问密码 91ac

Ⅵ 狄克斯特拉的简介

埃德斯加·狄克斯特拉
——最先察觉“goto有害”的计算机科学大师
首届计算机先驱奖获得者中有一位荷兰的计算机科学家埃德斯加·狄克斯特拉(Edsgar Wybe Dijkstra)。狄克斯特拉因最早指出“goto是有害的”以及首创结构化程序设计而闻名于世。事实上，他对计算机科学的贡献并不仅仅限于程序设计技术。在算法和算法理论、编译器、操作系统诸多方面，狄克斯特拉都有许多创造，作出了杰出贡献。1983年，ACM为纪念Communications of ACM创刊25周年，评选出从1958—1982年的四分之一个世纪中在该杂志上发表的25篇有里程碑意义的论文，每年一篇，狄克斯特拉一人就有两篇入选，是仅有的这样的两位学者之一(另一位是英国学者C．A．R．Hoare，也是计算机先驱奖获得者)。

Ⅶ 各位快来帮帮忙 关于Dijkstra算法的

楼主说的对，说明你在研究这个问题很好。最短路径就是是最小生成树的n-1条边！

Ⅷ OSPF的算法是什么

我们知道，对于有向连通图，以任意一个节点为起点，利用最短路径算法可以计算出到其他节点的最短路径。那么，对于能抽象成有向连通图的网络拓扑来说，也可以利用最短路径算法先计算出以任意一台路由器为起点，到达其他路由器的最短路径，然后根据各路由器的网络连接情况可以得到到各个网络的路由路径。
OSPF中用到的Dijkstra算法和RIP中用到的距离向量算法一样，都是相当经典的最短路径算法。本文将对Dijkstra算法及OSPF协议对Dijkstra算法的使用进行介绍。
1 Dijkstra算法介绍
在数学上，以某个节点为起点，计算到其他节点的最短路径的算法，称为“单源最短路径” 算法。求“单源最短路径”的问题在数学上可以精确描述如下：
“单源最短路径” 问题：已知一个有n个节点(V0..n)构成的有向连通图G=(V，E)，以及图中边的权函数C (E)，其中V代表节点集合，E表示所有边的集合，并假设所有权非负，求由G中指定节点V0到其他各个节点的最短路径。
Dijkstra算法是很经典的求解上述问题的算法，其基本想法是设计一种最短路径树的构造方法，按非降次序逐条构造从V0到各个节点的最短路径，第一步找到和V0相距最短的节点以及到这个节点的路径，第二步找到和V0相距次短的节点以及到这个节点的路径，如此反复，最后找到V0到所有节点的最短路径，构造出整棵最短路径树。
对上述构造方法的一个直观考虑是：和V0相距最短的节点应该在和V0直接相邻的节点中，和V0相距次短的节点要么在和V0直接相邻的节点中，要么在和这些相邻节点相邻的节点中，如此逐步扩散考虑，应该就可以找到和V0相距最短、次短、…….第n短的节点以及对应的路径，而且因为是连通图，最后肯定所有节点都能全部考虑到，也就能完成整棵最短路径树的构造。
事实上，上述直观考虑是对的，Dijkstra算法是对上述过程的一个提炼和优化：和V0相距最短的节点是和V0直接相连的节点没错;相距次短的节点范围可以缩小为，和V0直接相邻的节点，加上跟刚选中的最短节点直接相邻的节点;相距第三短的节点的范围可以类推得到，即在上一步考察的节点的基础上，加上和次短节点直接相邻的节点。如此逐步构造，可以按非降次序找到到所有节点的最短路径。
为了从数学上精确描述上述构造过程，引入了集合的概念对节点和路径进行分类。
我们把节点分成两个集合：
A：已经选入最短路径树的节点的集合。
B：剩余的其他节点的集合。
对于路径，我们分成三个集合：
(1)已经选入最短路径树的路径的集合
(2)候选路径集合：下一条加入最短路径树的路径将从这个集合中选入
(3)剩余的其他路径的集合(被废弃的路径或者还未考虑的路径)
为了更好的理解，有必要对这里的路径定义进行一下强调：路径是指以V0为起点，其他节点为终点的由一条或多条边组成的一个有序集。边，可以理解为路径中的一段，只有到和V0直接相邻的节点的路径才直接对应一条边。从V0到所有节点，都可能存在一条或多条路径，非最短路径在计算过程中将会被废弃，放入集合III。
从前面的描述中可以明显看出，Dijkstra算法是一个递归构造过程，因为任何递归都必须有明确的初始状态，所以我们有必要先得到上述Dijkstra算法中定义的集合的初始值：
l 以V0为起点计算最短路径的话，初始状态时显然有且只有V0在集合A中，所以集合A的初始值为V0。集合B的初始值为剩余节点。
l 前面提到过，下一个加入集合A的节点，一定是和V0直接有边相连的节点，因此，加入最短路径树的第一条路径也必然在这些和V0直接相连的边所代表的路径中产生，所以集合II的初始值就是和V0直接相连的边构成的路径。另外，初始状态最短路径树为空，所以集合I的初始值为空。集合I、II明确了的话，集合III自然明确。
下面我们开始展开递归构造最短路径树的过程：
l 第一步：从集合II中选择一条最短的路径，放入最短路径树，相应的，这条路径的终点对应的节点(这里记为X)应该从集合B移入集合A。
l 第二步：考察所有从X出发的边的终点，考虑其中不属于集合A的节点，这里记为Y，计算从V0出发经X到达Y的路径值，计算方法为：最短路径树中V0到节点X的路径值加上(X，Y)这条边的值。为了描述方便，我们把从V0出发经X到达Y的路径记为(V0X)Y。接着考察集合II中的候选路径，如果其中没有到节点Y的路径，则直接把路径(V0X)Y作为候选路径加入集合II;如果集合II中已经有到节点Y的路径，则进行比较，如果这条路径值小于或等于路径 (V0X)Y的路径值，那么路径(V0X)Y作为被废弃的路径放入集合III，否则原集合II中到Y的路径被废弃放入集合II，(V0X)Y作为候选路径放入集合II。对于Y节点有多个的情况，按第二步的方法一个一个的计算和比较。
l 重复第一步和第二步，直到集合II和集合B为空。

Ⅸ 关于图的最短路径问题

医院选址
1.
代码如下

#include <iostream>
using namespace std;
#define MAXV 50
#define INF 32767
typedef int InfoType;
//邻接矩阵存储方法
typedef struct
{
int no;
InfoType info;
} VertexType;
typedef struct
{
int edges[MAXV][MAXV];
int n,e;
VertexType vexs[MAXV];
} MGraph;
//狄克斯特拉算法
void Ppath(int path[],int i,int v)
{
int k;
k=path[i];
if(k==v) return;
Ppath(path,k,v);
cout<<k;
}
int biaoji1=0,biaoji2=0;
void Dispath(int dist[],int path[],int s[],int n,int v)
{
int i;
for(i=0;i<n;i++)
{
if(i==v) continue;
if(s[i]==1)
{
cout<<"从"<<v<<"到"<<i<<"的最短路径为："<<dist[i]<<" ";
cout<<v;
Ppath(path,i,v);
cout<<i<<endl;
if(biaoji1!=5)
{biaoji2+=dist[i];biaoji1++;}
else
{
cout<<"和为："<<" "<<biaoji2;
biaoji1=0;biaoji2=0;
}
}
else
cout<<"从"<<v<<"到"<<i<<"不存在的路径"<<endl;
}
}
void Dijkstra(MGraph g,int v)
{
int dist[MAXV],path[MAXV];
int s[MAXV];
int mindis,i,j,u;
for(i=0;i<g.n;i++)
{
dist[i]=g.edges[v][i];
s[i]=0;
if(g.edges[v][i]<INF) path[i]=v;
else path[i]=-1;
}
s[v]=1;path[v]=0;
for(i=0;i<g.n;i++)
{
mindis=INF;
for(j=0;j<g.n;j++)
{
if(s[j]==0&&dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
}
s[u]=1;
for(j=0;j<g.n;j++)
{
if(s[j]==0)
{
if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j])
{
dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
}
}
Dispath(dist,path,s,g.n,v);
}
//弗洛伊德算法
void Ppath1(int path[][MAXV],int i,int j)
{
int k;
k=path[i][j];
if(k==-1) return;
Ppath1(path,i,k);
cout<<k;
Ppath1(path,k,j);
}
void Dispath1(int A[][MAXV],int path[][MAXV],int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j) continue;
if(A[i][j]==INF)
{
if(i!=j)
cout<<"从"<<i<<"到"<<j<<"不存在路径"<<endl;
}
else
{
cout<<"从"<<i<<"到"<<j<<"的最短路径长度为:"<<A[i][j]<<" ";
cout<<i;
Ppath1(path,i,j);
cout<<j<<endl;
}
}
}
}
void Floyd(MGraph g)
{
int A[MAXV][MAXV],path[MAXV][MAXV];
int i,j,k;
for(i=0;i<g.n;i++)
{
for(j=0;j<g.n;j++)
{
A[i][j]=g.edges[i][j];
path[i][j]=-1;
}
}
for(k=0;k<g.n;k++)
{
for(i=0;i<g.n;i++)
{
for(j=0;j<g.n;j++)
{
if(A[i][j]>A[i][k]+A[k][j])
{
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
}
}
}
Dispath1(A,path,g.n);
}

//主函数
int main()
{
int i,j,n;
MGraph g;
cout<<"请输入带权有向图的顶点个数：";//6
while(scanf("%d",&n)!=EOF/*cin>>n,n!=EOF*/)
{
cout<<"请输入带权有向图的邻接矩阵："<<endl;
/*
0 5 32767 7 32767 32767
32767 0 4 32767 32767 32767
8 32767 0 32767 32767 9
32767 32767 5 0 32767 6
32767 32767 32767 5 0 32767
3 32767 32767 32767 1 0
*/

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
//scanf("%d",&g.edges[i][j]);
cin>>g.edges[i][j];
}
}
g.n=n;
cout<<"采用狄克斯特拉算法得到的最短路径为："<<endl;
for(i=0;i<n;i++) Dijkstra(g,i);
cout<<endl;
cout<<"采用弗洛伊德算法得到的最短路径为："<<endl;
Floyd(g);
cout<<endl;
cout<<"请输入带权无向图的顶点个数：";
}
return 0;
}

2.代码如下

#include <iostream>
using namespace std;
int INFTY=32767;
template<class T>
class Graph
{
public:
virtual void Insert(int u,int v,T& w)=0;
virtual void Remove(int u,int v)=0;
virtual bool Exist(int u,int v)=0;
virtual int Vertices()const {return n;}
protected:
int n,e;

};
template <class T>
class MGraph:public Graph<T>//邻接矩阵存储图
{
public:
MGraph();
~MGraph();
void Build_Graph();
void Insert(int u,int v,T& w);
void Remove(int u,int v);
bool Exist(int u,int v);
void Floyd(T**&d,int**&path);
int num;
protected:
T**a;
T noEdge;
};
template <class T>
void MGraph<T>::Build_Graph()//建图
{
cout<<"请输入顶点的个数："<<endl;
int C_num;
cin>>C_num;
num=n=C_num;e=0;noEdge=INFTY;
a=new T*[n];
for(int k=0;k<n;k++){
a[k]=new T [n];
for(int j=0;j<n;j++)a[k][j]=noEdge;
a[k][k]=0;
}
cout<<"建立村庄编号为1--"<<C_num<<"的图"<<endl;
for(int i=0;i!=C_num;i++)
for(int j=i+1;j!=C_num;j++)
{
int w;
cout<<"请输入村庄"<<i+1<<"与村庄"<<j+1<<"之间的权值：";
cin>>w;
Insert(i,j,w); //向图中添加权值为W的边
cout<<i<<"--->"<<j<<":"<<a[i][j]<<endl;
}
cout<<"*********************************************************************"<<endl;
cout<<"已建立村庄编号为1--"<<C_num<<"的图:"<<endl;
cout<<"**********************************"<<endl;
cout<<" \t\t";
for(int b=1;b<=C_num;b++){

cout<<b<<"\t";
}
cout<<endl;
}

template <class T>
MGraph<T>::MGraph()
{
Build_Graph();
}

template <class T>
MGraph<T>::~MGraph()
{
for(int i=0;i<n;i++)delete[]a[i];
delete[]a;
}

template <class T>
bool MGraph<T>::Exist(int u,int v)
{
if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==noEdge) return false;
return true;
}
template <class T>
void MGraph<T>::Insert(int u,int v,T &w)
{
a[u][v]=w;a[v][u]=w;e++;
}
template <class T>
void MGraph<T>::Remove(int u,int v)
{
a[u][v]=noEdge;e--;
}

template <class T>
void MGraph<T>::Floyd(T**&d,int**&path)//所有顶点之间的最短路径
{
int i,j,k;
d=new T*[n];path=new int*[n];
for(i=0;i<n;i++){
d[i]=new T[n];path[i]=new int[n];
for(j=0;j<n;j++){
d[i][j]=a[i][j];
if(i!=j&& a[i][j]<INFTY)path[i][j]=i;
else path[i][j]=-1;
}
}
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(d[i][k]+d[k][j]<a[i][j]){
d[i][j]=d[i][k]+d[k][j];
path[i][j]=path[k][j];
}
}
int main()
{
MGraph<int> Hospital;
int **d,**path;
int i,j,n;
n=Hospital.num;
Hospital.Floyd(d,path);
int *sum=new int[n];
cout<<endl;
for(i=0;i!=n;i++)//输出矩阵
{
cout<<i+1<<"\t\t";
sum[i]=0;
for(j=0;j!=n;j++)
{
sum[i]+=d[i][j];
cout<<d[i][j]<<"\t";
}
cout<<endl;
}
cout<<"*********************************************************************"<<endl;
int min=0;
for(i=0;i!=n;i++)
{
cout<<i+1<<"村庄："<<sum[i]<<endl;
if(sum[min]>sum[i])//判断最短路径
min=i;
}
cout<<"医院应在编号为"<<min+1<<"的村庄"<<endl;
for(i=0;i<n;i++)
{
delete[]d[i];
delete[]path[i];
}
delete[]d;
delete[]path;
return 0;
}

Ⅹ 狄克斯特拉算法的path是怎么算出来的

Dijkstra算法（狄克斯特拉算法） Dijkstra算法是由荷兰计算机科学家 狄克斯特拉 （ Dijk stra ）于1959 年提出的，因此又叫狄克斯特拉算法。 是从一个顶点到其余各顶点的最短路径算法， 解决的是有向图中最短路径问题。

程序如下，稍加改动即可。
带权有向图的最短路径的求解
//带权有向图的最短路径的求解
#include <stdio.h>
#include <stdlib.h>
#define MAXV 50
#define INF 32767
typedef int InfoType;
//邻接矩阵存储方法
typedef struct
{
int no;
InfoType info;
} VertexType;
typedef struct
{
int edges[MAXV][MAXV];
int n,e;
VertexType vexs[MAXV];
} MGraph;
//狄克斯特拉算法
void Ppath(int path[],int i,int v)
{