网站建站视频搜索引擎优化概述

无向图的最短路径

请问各位大牛无向图的最短路径应该怎么求啊？权值默认为1，想破脑子也没想出来应该怎么办。。。我看了几种算法，不知道是我太笨还是怎么地，没想出来

图

分享到：

------解决方案--------------------

无向图的最近路径分为单源(从一个节点出发)和多源(网络中任意两个节点间)，如果单源最短路径，最常用的算法就是Dijkstra算法。

------解决方案--------------------

如果路径权值都为1。。。直接对每一个点进行一次广度优先搜索就可以了。。

如果是一般的图，就用floyd算法。。这个写起来简单。。

------解决方案--------------------

floyd算法。。G是图的邻接矩阵。。

int G[N][N];

for(int k = 0; k 

for(int i = 0; i 

for(int j = 0; j 

if(G[i][j] > G[i][k] + G[k][j]) G[i][j] = G[i][k] + G[k][j];

}

}

}

------解决方案--------------------

floyd算法 或者Dijkstra算法

这个是floyd

#include 

int main(void)

{

int k,m;

int i,j,e;

int u,v,w;

while(scanf("%d %d",&k,&m)!=EOF)

{

int a[110][110];

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

{

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

{

a[i][j] = 65535;

}

}

while(m--)

{

scanf("%d %d %d",&u,&v,&w);

a[u][v] = w;

a[v][u] = w;

}

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

{

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

{

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

{

if(a[i][e]<65535 && a[e][j]<65535 && a[i][j]>a[i][e]+a[e][j])

a[i][j] = a[i][e] + a[e][j];

}