1.两地之间是否有通路?
2.若存在多条通路，哪条路最短？
●单源最短路径
Single-Source Shortest Path
(Dijkstra算法)
负权边的有向图单源最短有路径
Bellman-Ford算法
●所有顶点对间的最短路径问题
All-Pairs Shortest paths （Floyd算法）
●问题: 带权有向图G（E,V), 找出从给定源顶点s到其它顶点v的权最小路径。
●“最短路径” = 最小权
在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。确定起点的最短路径问题：即已知起始结点，求最短路径的问题。
Dijkstra算法
Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
如下图：
●贪心算法：
基于以下原理：若顶点序列{Vs,V1,…,Vn} 是从Vs到Vn的最短路，则序列 {Vs,V1,…,Vn-1} 必为从Vs到Vn-1的最短路。
●基本思想：
设置一个顶点集S，不断做贪心选择扩充这个集合。
一个顶点属于S当且仅当从源到该顶点最短路径长度已知。
●图中从v0到其余各顶点之间的最短路径:
v0到 v1 无
v0到 v2 (v0,v2) 10
v0到 v3 (v0,v4,v3) 50
v0到 v4 (v0,v4) 30
v0到 v5 (v0,v4,v3,v5) 60
● 初始时,S仅包含源s,
● 特殊路径：
从源到G中某一顶点u且中间只经过S中顶点的路称为从源到u的特殊路径。
● 算法每次从V-S中取出具有最短特殊路径
长度的顶点u加入S中。
●算法思想:
按路径长度递增序产生各顶点最短路径
用到的变量：
int G[maxnum][maxnum]; //邻接矩阵,距离无限远用9999表示
int dist[maxnum]; //存放各个顶点到源点的寻短路径；
bool visit[maxnum] ; //标志该定点是否被访问，初始化wei 0
int last;//表示当前所走路径最后一个节点
利用贪心算法，首先从原点出发，初始化dist[maxnum]; 假如源点v0，顶点数目6 (v0,v1,v2,v3,v4,v5)；
for i=0 to 5 ,dist[i]=G[0][i];
然后dist[0] = 0;//到本身距离为0， 再标记V0点， visit[0] = 1;//以访问v0点，
此时dist[5]={0,9999,30,9999,30,100}; visit[]={1,0,0,0,0,0}; last = 0;//v0点为当前路径最后一个
然后for循环，寻找从源点到其他店的最小距离，并且该点未被访问，
int min = 9999;
for(j=0;j<n;j++)
{
if(!visit[j] && min< G[v0][j])
{
min = G[last][j];
last = j;
}
}
得到 last=2；//将v2加入当前路径 ， visit[last] = 1;
visit[] = {1,0,1,0,0,0}
然后将dist[]数组更新。, 更新为V0到各个点的最短路径
然后循环，直到所有结点都被访问；
for(j=0;j<n;j++)
{
if(!visit[j] && G[last][j]!=99999)
{
int newdist = dist[last] + G[last][j];
if(newdist < dist[j])
{
dist[j] = newdist;
prev[j] = last;
}
}
}
#include <iostream>
using namespace std;
void Dijkstra(int n,int v,int *dist,int *prev,int G[102][102])
{
bool visit[102];//存放顶点是否被访问
int i,j;
for(i=1; i<=n; i++)
{
visit[i] = 0;
dist[i] = G[v][i];
if(dist[i]== 99999) prev[i] = 0;
else prev[i] = v;
}
dist[v] = 0;
visit[v] = 1;
for(i=2;i<=n;i++)//访问剩下的点
{
int last = v;
int min = 99999;
//寻找本行未使用点j的dist[j]最小值
for(j=1;j<=n;j++)
{
if(!visit[j]&& min>dist[j])
{
min = dist[j];
last = j;//距离最小点的号码
}
}
visit[last] = 1;//访问该距离最小点
//将dist[]刷新
for(j=1;j<=n;j++)
{
if(!visit[j] && G[last][j]!=99999)
{
int newdist = dist[last] + G[last][j];
if(newdist < dist[j])
{
dist[j] = newdist;
prev[j] = last;
}
}
// printf("%d ",dist[j]);
}
// printf("\n");
}
}
int main()
{
int i,j,a,b,c;
int dist[102];
int prev[102]; //记录当前点的前一个结点
int G[102][102];
int vnum,m;
while(scanf("%d%d",&vnum,&m),m&&vnum)
{
for(i=1;i<=vnum;i++)
for(j=1;j<=vnum;j++)
G[i][j] = 99999;
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
G[a][b] = G[b][a] = c;
}
for(i=1;i<=vnum;i++)
dist[i] = 99999; //原点到各个点距离初始化
// for(i=1;i<=vnum;i++) //输出创建的邻接矩阵
// {
// for(j=1;j<=vnum;j++)
// printf("%4d",G[i][j]);
// printf("\n");
// }
Dijkstra(vnum,1,dist,prev,G);
printf("%d\n",dist[vnum]);
}
return 0;
}