最短路径算法

⑴ 最短路径算法作用

可以实现距离最短以及时间最短，从而为你节约行程的成本

⑵ "最短路径优先算法"的优缺点

这个算法一般出现在网络中，用于路由器的路由寻址，我也只了解这方面的优缺点。如果不对，LZ就别看了。
所谓最短路径，实际上说的是跳数。比如从一条路走会经过三个路由器，而从另一条路走，会经过两个路由器，那么此算法会判断2跳比3跳要短，但具体每一跳会花多长时间，经过多长路程，它不会考虑的。所以不一定算法的最短路径就是真实的最短。因为很多因素算法没有考虑，比如通信质量，网线长度……
C语言我只看过一个模拟现实的例子，大概是说公车走什么路线长度最短，那个算法考虑的是路线的长短，而不是跳数，优点当然就是路线的绝对最短，缺点就是没考虑到其他现实因素，比如是否堵车（相当于网络通信质量）之类。
总之不管什么算法，考虑到的因素就是它的优点，反过来说，缺点往往就是算法忽略的因素。
补充一下，如果说的不是算法本身的优劣，而是细节的实现方面，那就是从时间复杂度和空间复杂度两个方面去考虑了，希望对LZ有用。

⑶ 最短路径算法 Dijkstra 用C语言编出来

#include"iostream.h"
#include"stdlib.h"
#define MAXPOINT 3//定义最大的顶点数目

#define limit 32767 //设置没有路径的权代替无穷大

struct record{ //没个顶点的数据结构设置为一个数组队列
int number; //顶点号
int flag; //标志是否从队列中被选过如果为1表示选过为0表示未选
int allpath; //从源点到这个点的当前最短距离（权最小）
}path[MAXPOINT+1];

int cost[MAXPOINT+1][MAXPOINT+1]; //用来表示图的邻接矩阵

void main()
{int i,j,temp,front=1,rear=MAXPOINT,N,minnumber;
//temp表示在数组队列中的当前下标 front表示队列首 rear表示队列尾
//N 表示待输入的源点号码 minnumber 表示选中的点的号码
int min=32768; //设置一个初始值
for(i=1;i<=MAXPOINT;i++)
for(j=1;j<=MAXPOINT;j++)
{cout<<"请输入从第"<<i<<"点到第"<<j<<"点的路径长度(权)如果没有路径的话请输入'32767' "<<endl;
cin>>cost[i][j]; //初始化所有点之间的（权）路径值
}

//cout<<"请输入源点号"<<endl; //输入一个起点
//cin>>N;

for(N=MAXPOINT;N>=1;N--)//把每一个点轮流地都设置为起点，可以求出任意一对顶点之间的最短路径

{ for(i=front;i<=rear;i++) //初始化每个点的信息
{if(i==N)
path[i].allpath=0;
else
path[i].allpath=limit;
path[i].flag=0;
path[i].number=i;
}

while(rear>=1) //控制循环次数
{for(temp=front;temp<=MAXPOINT;temp++)
{ if(path[temp].allpath<min&&path[temp].flag==0)//选出一个具有最值
//的点

{ minnumber=path[temp].number;
min=path[temp].allpath ;
}

}
min=32768;

path[minnumber].flag=1;//把选中的点的标志变量置1表示已经被选过避免选中

for(i=1;i<=MAXPOINT;i++)//进行类似广度优先搜索，更新最短路径
{if((i!=minnumber)&&(path[minnumber].allpath+cost[minnumber][i]<path[i].allpath))
path[i].allpath=path[minnumber].allpath+cost[minnumber][i];
}

rear--;//次数减1
}
rear=MAXPOINT; //恢复数组以便于下一点的循环
for(j=1;j<=MAXPOINT;j++)
{ cout<<"第"<<N<<"点到第"<<j<<"点的最短路径长度（权）为";
cout<<path[j].allpath <<endl;
}

}

}

//这个程序可以求出任意一对顶点之间的最短路径，不过这种算法效率还不是很高，还有其他算法待续

⑷ 最短路径算法应用在哪些方面

网络通路， 凡事可以使用图作为模型的问题都基本可以用到，比如游戏地图的寻找，交通路线的寻找，这种最短路径都可以用。

⑸ 求图中任意两点之间最短路径有什么算法

单源节点到其他任意节点的最短路径采用Dijkstra算法，任意两个节点之间的最短路径使用Floyd算法，这两个算法有很多地方可以找打。

⑹ 最短路径优先算法

从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。解决最短路的问题有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法等。

⑺ 记录所有最短路径的最短路径算法

没有一个算法是万能的
Dijkstra:单源最短路径
Floyd:每对点最短路径
SPFA(Bellmanford+队列):快速单源最短路径(可负权)
还有很多求最短路径的算法，但是归其根本，无外乎：
Label Setting和Label Correcting两大类，其实就是搜索法+动态规划。
只要灵活地掌握了搜索法、动态规划和图论，这些算法就都会了。

⑻ 最短路径算法 C语言

#include<stdio.h>

#defineMAXNODE108

intpath[MAXNODE+1][MAXNODE+1]={0};

intmain(void)
{
FILE*fpr,*fpw;
intva,vb,i,j,k;

fpr=fopen("in.txt","r");/*读取的文件名称in.txt*/
fpw=fopen("out.txt","w");/*path的数据在out.txt中展现*/

while(fscanf(fpr,"%d%d",&va,&vb)!=EOF)
path[va][vb]=path[vb][va]=1;

for(k=1;k<=MAXNODE;++k){
for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(!path[i][k]||!path[k][j])
continue;

if(!path[i][j])
path[i][j]=path[i][k]+path[k][j];
elseif(path[i][j]>path[i][k]+path[k][j])
path[i][j]=path[i][k]+path[k][j];
}
}
}

for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(i==j)
fprintf(fpw,"%-10d",0);
elseif(path[i][j])
fprintf(fpw,"%-10d",path[i][j]);
else
fprintf(fpw,"%-10d",-1);
}
fprintf(fpw,"
");
}

return0;
}

注意：floyd算法中k为最外层，这是动态规划的思想，不能改变i,j,k的顺序！！！

这是之前的答案的错误之处。

-1表示不通。

具体程序分析，我可以加你QQ，愿意的话，你把QQ写给我。