求最短路径（Floyd算法和Dijkstra算法）
一、Floyd算法
假设 _vertex[i][j] 表示节点 i 到节点 j 的最短距离，那么在图中遍历其它的点 k 时，如果 _vertex[i][k] + _vertex[k][j] < _vertex[i][j] 时，就对 _vertex[i][j] 进行更新，即 _vertex[i][j] = _vertex[i][k] + _vertex[k][j]，和动态规划的思想一样；
假设 _vertexPath[i][j] 记录节点 i 到节点 j 的路径中最后一个节点，或者说最后一个节点的前一个节点（如果包括正在计算的节点j的话），那么在更新 _vertex 的时候，就可以记录下路径的最后一个节点。
代码如下：
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define LOOP( X, Y ) for( int X = 0; X < Y; X++ )
const LL MAX = 999999;
LL nodes = 0, egdes = 0;
void Floyd( vector< vector<int> >_vertex, vector< vector<int> >_vertexPath, LL nodes );
void PrintPath( int i, int j, vector< vector<int> >_vertex, vector< vector<int> >_vertexPath, LL nodes );
int main()
{
cin>>nodes>>egdes;
vector< vector<int> >_vertex( nodes, nodes );
vector< vector<int> >_vertexPath( nodes, nodes );
LOOP( i, nodes )
{
LOOP( j, nodes )
{
_vertex[i][j] = MAX; //初始两个节点之间的距离为无穷大
}
}
Floyd( _vertex, _vertexPath, nodes );
LL start = 0, destinate = 0;
cin>>start>>destinate;
PrintPath(start, destinate, _vertex,_vertexPath,nodes);
return 0;
}
void Floyd( vector< vector<int> >_vertex, vector< vector<int> >_vertexPath, LL nodes )
{
LOOP( i, nodes )
{
LOOP( j, nodes )
{
_vertexPath[i][j] = i; //初始节点i到节点j的路径最后一个节点为i
}
}
LOOP( i, nodes )
{
LOOP( j, nodes )
{
LOOP( k, nodes )
{
if( _vertex[i][j] > _vertex[i][k] + _vertex[k][j] )
{
_vertex[i][j] = _vertex[i][k] + _vertex[k][j]; //更新最短路径的值
_vertexPath[i][j] = k; //记录节点i到节点j的最短路径中最后一个节点，或者说最后一个节点的前一个节点（如果包括正在计算的节点j的话）
}
}
}
}
return;
}
//输出路径函数，
//参数说明： i ： 表示起始点
// j ： 表示终点
void PrintPath( int i, int j, vector< vector<int> >_vertex, vector< vector<int> >_vertexPath, LL nodes )
{
stack<int> Path;
if( i != j ) //如果起点和终点不同才输出
{
cout<<_vertex[i][j]<<endl;
LL k = j;
do
{
k = _vertexPath[i][k];
Path.push(k); //因为每次存放的是最后一个节点，所以路径是倒着的，所以使用一个栈进行存储，反过来输出。
}while( k != i );
cout<<Path.top()+1;
while( !Path.empty() )
{
cout<<"->"<<Path.top()+1;
}
cout<<endl;
}
return ;
}
二、Dijkstra算法
设dist[i] 表示点 i 到原点source的最小距离，pass[i] 记录遍历过的点，1表示遍历过得，0表示未遍历，prev[i] 记录第 i 个节点的前一个节点，v[i][j] 表示节点 i 到节点 j 之间的距离，不可达的话，距离为MAX，步骤如下：
1、令u动态地表示起始点，刚开始 u = source，对 dist[i] 进行初始化，u不可到达的点，dist[i] = MAX，可到达的点，则dist[i] = v[u][i]， 同时记录节点 i 的前一个节点prev[i]， 若节点可达，则prev[i] = u，否则prev[i] = -1，最后将 pass[u] = 1，表示原点已经遍历过了。
2、对 u 周围的节点进行遍历，选择出距离节点 u 最短的节点 j ，这时 u = j，更新起始点，将prev[j] = source， 并将 pass[j] = 1；
3、对所有的节点进行遍历，判断 dist[j] > dist[u] + v[u][j] 是否满足，即判断通过节点 u 到达节点 j 是否为最短的，如果满足条件，则对 dist[j] 进行更新，并将prev[j] = u。
代码如下：
#include <iostream>
#include <vector>
using namespace std;
#define LL long long
const LL MAX = 999999999;
void Dijkstra( int nodes, int s, vector<LL> &dist, vector<int> &prev, vector< vector<int> > v )
{
vector<bool> passed(nodes);
for( int i = 0; i < nodes; i++ )
{
dist[i] = v[s][i];
passed[i] = false; //初始每个节点都未遍历过
if( dist[i] == MAX )
prev[i] = -1;
else
prev[i] = s;
}
dist[s] = 0; //初始s到s的距离为0
passed[s] = true; //初始s已经遍历过
//依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中
//一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度
for( int i = 1; i < nodes; i++ )
{
LL temp = MAX;
int u = s;
//找出当前未使用的点j的dist[j]最小值
for( int j = 0; j < nodes; j++ )
{
if( (!passed[j]) && dist[j] < temp )
{
u = j;
temp = dist[j];
}
}
passed[u] = true; //把邻接点中距离最短的点加入到passed中
更新dist
for( int j = 0; j < nodes; j++ )
{
if( (!passed[j]) && (v[u][j] < MAX) )
{
LL newdist = dist[u] + v[u][j];
if( newdist < dist[j] )
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}
}
int main()
{
freopen("Dijkstra.in", "r", stdin);
int nodes = 0;
long long edges = 0;
cin>>nodes;
cin>>edges;
vector< vector<int> >v(nodes,nodes); //定义邻接矩阵
vector<LL> dist(nodes); //记录当前节点到源节点的最短路径长度
vector<int> prev(nodes); //记录当前节点的前一个节点
for( LL i = 0; i < nodes; i++ )
{
for( LL j = 0; j < nodes; j++ )
{
v[i][j] = MAX; //初始化将两点之间的距离为MAX
}
}
int p = 0, q = 0, len = 0;
for( int i = 0; i < edges; i++ )
{
cin>>p>>q>>len;
v[p-1][q-1] = len;
v[q][p] = len; //加上这句，表示无向图
}
for( int i = 0; i < nodes; i++ )
{
dist[i] = MAX; //初始化每个节点到源节点的路径长度为MAX
}
Dijkstra(nodes, 3, dist, prev, v); //参数：节点个数， 源节点， dist数组，prev数组，v邻接矩阵
cout << "源点到最后一个顶点的最短路径长度: " << dist[nodes-1] << endl;
return 0;
}