//最短路径 /*
dijkstraDijkstra(迪杰斯特拉)算法的核心思想是贪心策略+动态规划 http://www.programgo.com/article/4721147659/ Dijkstra算法能得出最短路径的最优解，但是效率低 */
Floyed 算法：
Floyed算法比较简单，其思想可以参照三角形的特性中，两边和与第三边的关系,a 和 b的最短路径要么是（a,b)要么是(a,c,b)，这取决于 a->b和a->c->b的大小。
算法思想原理：
Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）
从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。
/* 用邻接矩阵表示的图的Dijkstra算法的源程序*/ #include <iostream> using namespace std; #define MAXVEX 100 #define MAX 1e+8 typedef char VexType; typedef float AdjType; typedef struct { int n; //图的顶点个数 // VexType vexs[MAXVEX]; //顶点 AdjType arcs[MAXVEX][MAXVEX]; //边 }GraphMatrix; typedef struct { // VexType vertex; //顶点信息 AdjType length; // 最短路径长度 int prevex; // 从v0到达vi(i=1,2,…n-1)的最短路径上vi的前驱顶点 }Path; Path dist[6]; // n为图中顶点个数 void dijkstra(GraphMatrix graph, Path dist[]) { int i,j,minvex; AdjType min; // 初始化，此时集合U中只有顶点v0 dist[0].length = 0; dist[0].prevex = 0; graph.arcs[0][0] = 1; // 表示顶点v0在集合U中 for(i = 1; i < graph.n; i++) { // 初始化集合V-U中顶点的距离值 dist[i].length=graph.arcs[0][i]; if (dist[i].length != MAX) dist[i].prevex=0; else dist[i].prevex= -1; } for(i = 1; i < graph.n; i++) { min=MAX; minvex=0; for (j = 1; j < graph.n; j++) //在V-U中选出距离值最小顶点 if( graph.arcs[j][j] == 0 && dist[j].length < min ) { min=dist[j].length; minvex=j; } if(minvex == 0) break; // 从v0没有路径可以通往集合V-U中的顶点 graph.arcs[minvex][minvex] = 1; // 集合V-U中路径最小的顶点为minvex for (j = 1; j < graph.n; j++) { // 调整集合V-U中的顶点的最短路径 if(graph.arcs[j][j] == 1) continue; if(dist[j].length > dist[minvex].length + graph.arcs[minvex][j]) { dist[j].length = dist[minvex].length + graph.arcs[minvex][j]; dist[j].prevex = minvex; } } } } GraphMatrix graph; void initgraph(){ int i,j; graph.n=6; for (i = 0; i < graph.n; i++) for (j = 0; j < graph.n; j++) graph.arcs[i][j] = (i == j ? 0 : MAX); graph.arcs[0][1] = 50; graph.arcs[0][2] = 10; graph.arcs[1][2] = 15; graph.arcs[1][4] = 5; graph.arcs[2][0] = 20; graph.arcs[2][3] = 15; graph.arcs[3][1] = 20; graph.arcs[3][4] = 35; graph.arcs[4][3] = 30; graph.arcs[5][3] = 3; graph.arcs[0][4] = 45; } int main(){ int i; initgraph(); dijkstra(graph, dist); for (i = 0; i < graph.n; i++) printf("(%.0f %d) ", dist[i].length,dist[i].prevex); system("pause"); return 0; }
//============================================================================ //Floyed: 往点中间插入其他点，动态：s[i][k] + s[k][j] < s[i][j] //test case / //============================================================================ #include <iostream> using namespace std; int main() { int n,m,i,j,k,l,r; cout<<"输入结点数和边数 "; cin>>n>>m; int**s=new int*[n];//确定的是行数 for(int i=0;i<n;i++) { s[i]=new int[n];//确定的是列数 } //初始化，将自己与自己的距离置为0，任意两点距离置为99999 for(i=0;i<n;i++){ for(j=0;j<n;j++) { if(i==j) s[i][j]=0; s[i][j]=99999; } } //Input: cout<<"输入结点和两个结点的权值 "; for(k=0;k<m;k++) { cin>>i>>j; cin>>s[i][j]; } for (k=0; k<n; k++) for (i=0; i<n; i++) for (j=0; j<n; j++) if (s[i][k] + s[k][j] < s[i][j]) s[i][j] = s[i][k] + s[k][j]; cout<<"输入起始和终止结点"<<endl; cin>>l>>r; cout<<s[l][r]<<endl; system("pause"); return 0; } * 10 16 0 1 4 0 2 1 1 4 9 1 5 8 2 4 6 2 3 1 2 6 8 3 5 4 3 6 7 6 8 5 4 7 5 4 8 6 5 7 8 5 8 6 7 9 7 8 9 3 */