java 无向图 最短路径,无向图最短路径算法 - osc_qguxi63b的个人空间 - OSCHINA - 中文开源技术交流社区...

#include

#include

using namespace std;

///本题找的是顶点1到其他各个点之间的最短路径，并将最短路径存放在dis[]这个数组里面，最后只要遍历输出这个数组就可以得到

int main()

{

int inf=9999999;//表示无穷大，就是两个顶点之间没有链接

int e[10][10];///表示邻接矩阵,记住一定不要把数组开的特别大，如[1000][1000],就是程序卡顿，异常闪退

int dis[10];//表示顶点1到各个顶点之间的距离

int book[10];//标记该定点是否是被访问

int n,m;//顶点数和边数

int v1,v2,length;//表示两个顶点以及之间的距离

int min;///最小距离

int u;///为标记的点中dis[i]值最小时对应的i,就是dis数组中元素最小的下标值

cin>>n>>m;

int i,j,k;

for(i=1;i<=n;i++)///构建一个邻接矩阵

for(j=1;j<=n;j++)

{

if(i==j)

e[i][j]=0;

else

e[i][j]=inf;

}

for(i=1;i<=m;i++)///构建边，注意这里构建的是有向图，而不是无向图

{

cin>>v1>>v2>>length;

e[v1][v2]=length;///有向图

}

for(i=1;i<=n;i++)///初始化dis数组,这里要求的是1号顶点到其余各点的初始路程

{

dis[i]=e[1][i];

}

///初始化book数组,这里面存的是已经被标记过的点

for (int i = 1; i <= n; i++)

book[i] = 0;

book[1] = 1;///表示1点是已经被标记过的点

///核心代码

for(i=1;i<=n-1;i++)

{

min=inf;

for(j=1;j<=n;j++)

if(book[j]==0&&dis[j]

{

min=dis[j];

u=j;

}

book[u]=1;

for(k=1;k<=n;k++)

{

if(e[u][k]

{

if(dis[k]>dis[u]+e[u][k])

dis[k]=dis[u]+e[u][k];

}

}

}

for(i=1;i<=n;i++)

cout<

return 0;

}

///输入以下

/*

6 9

1 2 1

1 3 12

2 3 9

2 4 3

3 5 5

4 3 4

4 5 13

4 6 15

5 6 46

*/