对dijkstra和Floyd算法的理解

算法的理解"/>

对dijkstra和Floyd算法的理解

算法的适应范围

Floyed  算法：

弗洛伊德算法是解决任意两点间的最短路径的一种算法，可以正确处理无向图或有向图或负权（但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭包。

Floyed算法允许图中有带负权值边，允许有回路，但不允许有带负权值边的回路。

Dijkstra算法：

Dijkstra算法只适用于正权图的单源最短路。而对于存在权值为负的边的图，我们用的是SPFA(Shortest Path Faster Algorithm)算法（队列优化后的Bellman-Ford）。

ps:含负权的图中最短路不一定存在。显而易见，若一个图中存在一个负环，则最短路不存在。这是我们需要注意的一点。

算法的具体操作

用算法之前的建图二者是一样的，首先对map[][]进行初始化

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
map[i][j]=(i==j?0:INF);

如果路是双向的，就赋值map[i][j]=map[j][i]=权值，如果路是单向的，就赋值map[i][j]=权值。

Dijkstra算法：

这个算法和求最小生成树的prim算法很像（对prim算法的理解 ），唯一不同的就是对距离数组dis的更新。

dis[i]：x到n的最短路的距离。

void dijkstra(int x)
{int i,j;for(i=1;i<=n;i++)dis[i]=map[x][i];vis[x]=0;for(i=1;i<=n;i++){int min=INF;int temp;for(j=1;j<=n;j++)if(vis[j]&&dis[j]<min){min=dis[j];temp=j;}vis[temp]=0;for(j=1;j<=n;j++)if(vis[j]&&dis[temp]+map[temp][j]<dis[j])dis[j]=dis[temp]+map[temp][j];}
}

Floyd算法：

map[i][j]:i到j的最短路的距离。

void floyd()
{int i,j,k;for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i!=k&&i!=j&&k!=j)map[i][j]=minn(map[i][j],map[i][k]+map[k][j]);		
}