hdoj 2544

单源最短路径：从一个源头出发到所有点的最短路径

BFS只能求无权重图的单源最短路径

最优子结构：两个节点间的最短路径必然包含其他最短路径（最优子结构可以使用贪心和动态规划）

只要不包含一个权值为负的环路，负的最短路径就是有意义的。否则，再走一遍最短路径就能实现更小的权重.

最短路径不包含环。如果包含环，环是负的，那么没有最短路径；环是正的或者为0，删去环得到更小路径。可以假设最短路径不包含环路。任意无环路最多包含N个不同的节点，最多包含N-1条边。

Dijkstra算法：边的权重非负的图

最优子结构。从源点V0出发，考察附近的所有边，其中权值最小边连接的顶点为V1,则W01一定是V0到V1的最短路径（由于边的权重非负）。然后从V0出发，考察和V0连接的所有点，它们的最小者为V2，那么V0->V1->V2一定是V0到V2的最短路径（最优子结构）。如此直到遍历所有顶点为止。

（dijkstra必然会遍历所有顶点，O(VE)，通过isvisit数组来判断是否遍历）

迪克斯特拉特别坑，要走遍所有顶点，几乎是一个O(n^n)算法

HDOJ2544

垃圾迪克斯特拉版

#include <iostream>
using namespace std;
int map[105][105];
int dis[105];
bool isvisited[105];
int n,m;
#define INF 99999;
int min(int x,int y){if(x>y) return y;return x;
}
void Dijkstra()  
{  isvisited[1]=true;int i,p,j,min;  for (i=1;i<=n;i++)  //外面套一层循环，保证能够走遍所有的点(每次找一个dis最小的顶点，必然能遍历所有顶点){  min=INF;  for (j=1;j<=n;j++)  {  if(!isvisited[j] && dis[j]<min)  {  p=j;  min=dis[j];  }  //找到最小的dis未访问过的}  visited[p]=1;  for (j=1;j<=n;j++)  {  if(!visited[j] && dis[p]+map[p][j]<dis[j])  {  dis[j]=dis[p]+map[p][j];  }  }  //更新最小dis的相邻顶点}  
}  int main(int argc, char const *argv[])
{int a,b,c;while(cin>>n>>m){if(n==0) break;memset(isvisited,false,sizeof(isvisited));for(int i=0;i<=n;i++)for(int j=0;j<=n;j++){
<span style="background-color: rgb(255, 255, 255);">				map[i][j]=INF;
</span>				dis[i]=INF;}for(int j=0;j<m;j++){cin>>a>>b>>c;map[a][b]=map[b][a]=c;}for(int i=1;i<=n;i++){map[i][i]=0;dis[i]=map[1][i];}Dijkstra();cout<<dis[n]<<endl;}return 0;
}

spfa版本

#include <iostream>
#include <queue>
using namespace std;
#include <cstdio>
const int maxn=120;
const int INF=0xfffffff;
int matrix[maxn][maxn];
int dis[maxn];
queue<int> Q;
int N,M;
bool visit[maxn];
void spfa(){dis[1]=0;visit[1]=true;Q.push(1);while(!Q.empty()){int cur=Q.front(); Q.pop();visit[cur]=false;for(int i=1;i<=N;i++){if(dis[i]>matrix[i][cur]+dis[cur]){dis[i]=matrix[i][cur]+dis[cur];if(!visit[i]){visit[i]=true;Q.push(i);}}}}
}
int main(int argc, char const *argv[])
{int a,b,c;while(scanf("%d%d",&N,&M),N!=0){for(int i=1;i<=N;i++){dis[i]=INF;visit[i]=false;for(int j=1;j<=N;j++){matrix[i][j]=INF;if(i==j)matrix[i][j]=0;}}for(int i=0;i<M;i++){scanf("%d%d%d",&a,&b,&c);matrix[a][b]=matrix[b][a]=c;}spfa();printf("%d\n",dis[N]);}return 0;
}