描述：小明到小华家有许多条路可以走，现在给出所有能够到达他家的路线，并给出每条线段的长度，求出小明到小华家的最短路线！
介绍第一种学习方法：dijkstra算法
顶点集分为两组，第一组为：已求出最短路径的顶点集合
第二组为：其余未确定最短路径的顶点集合
按照最短路径长度递增次序把第二组中的顶点依次加入到第一组中
#include#include #include #include #include #include #include using namespace std;#define N 110#define MAX 999999#define CLR(arr, what) memset(arr, what, sizeof(arr))int nodenum, edgenum; int map[N][N], dis[N];bool visit[N];int Dijkstra(int src, int des){ int temp, k; CLR(visit, false); int i = 1 ; for(; i <= nodenum; ++i) dis[i] = (i == src ? 0 : map[src][i]); visit[src] = true; dis[src] = 0; for(i = 1; i<= nodenum; ++i) { temp = MAX; int j = 1 ; for(; j <= nodenum; ++j) if(!visit[j] && temp > dis[j]) temp = dis[k = j]; if(temp == MAX) break; visit[k] = true; for(j = 1; j <= nodenum; ++j) if(!visit[j] && dis[j] > dis[k] + map[k][j]) dis[j] = dis[k] + map[k][j]; } return dis[des];}int main(){ int start, end, cost; int answer; while(~scanf("%d%d", &nodenum, &edgenum) && (nodenum + edgenum)) { int i = 1 ; for(; i <= nodenum; ++i) for(int j = 1; j <= nodenum; ++j) map[i][j] = MAX; for(i = 1; i <= edgenum; ++i) { scanf("%d%d%d", &start, &end, &cost); if(cost < map[start][end]) map[start][end] = map[end][start] = cost; } answer = Dijkstra(1, nodenum); printf("%d\n", answer); } return 0;}