学c++的朋友一起看下..最短路径路由算法的..用Dijkstra算法解决帮我看下下面这段代码..

来源:百度知道 编辑:UC知道 时间:2024/04/27 21:17:19
/***********************************************
设G=(V,E)是一个每条边都有非负长度的有向图,有一个特异的顶点s称为缘。
单源最短路径问题,或者称为最短路径问题,是要确定从s到V中每一个其他
顶点的距离,这里从顶点s到x的距离定义为从s到x的最短路径问题。这个问题
可以用Dijkstra算法解决。下面我给我了c++下的源代码! --by 伟伟猪
************************************************/
#include<iostream.h>
#include<fstream.h>
#include<iomanip.h>
void main()
{
int infinity=100;//无穷大
int i,j,n,k,t,**w,*s,*p,*d;
cout<<"input the value of n:";//顶点个数为n
cin>>n;
cout<<endl;

d=new int[n];//d指针指向d[0] 保存最后路径用
s=new int[n];//s指针指向s[0];
p=new int[n];//p指针指向p[0] 过渡矩阵
w=new int*[n];//w指针指向*w[0]
for(i=0;i<n;i++)
{
w[i]=new int[n];//w[i]指向w[i][0];
}
//相当 于定义了数组 d[n],s[n],p[n],w[n][n]
/*for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];//输入的是邻接矩阵*/
ifstream is("chineselin.txt",ios::in| ios::nocreate);

dijkstra算法的思想是DP+贪心.
每次寻找“最近点”扩展并更新状态

for(i=1;i<n;i++)//扩展n-1次
{
t=infinity;
k=1;
for(j=1;j<n;j++)//这里是为了寻找“最近点”,即d[k]最小
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;
}
}

不知道LZ还有哪里不清楚的