有向图的最短路径算法
⑴ 求有向图最短路径算法（权重可为负）
单元最短路径：
1.如果没有负权环的稀疏图，可以用SPFA，时间复杂度O（KM）
M是边数，K是平均入队列的次数
2.如果没有负权环的稠密图，建议用Dijkstra O（N^2），用二叉堆可优化到
O（NlogN），斐波那契堆编程复杂度太高，不易于实现
3.如果有负权环，可以尝试floyd,O(n^3)
任两点最短路径：floyd较好实现，基于重标号johnson也不错（稀疏图效率高）
具体程序可以上网查
⑵ 最短路径问题5种类型
最短路径问题5种类型有Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法，
扩展知识：
用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：
Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法，本文主要介绍其中的三种。
最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
算法具体的形式包括：确定起点的最短路径问题：即已知起始结点，求最短路径的问题。
确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。
⑶ 求有向图两个顶点间的最短路径的方法，用简单语言或举例描述。
在交通网络中，常常会提出许多这样的问题：两地之间是否有路相通？在有多条通路的情况下，哪一条最近？哪一条花费最少等。交通网络可以用带权图表示，图中顶点表示域镇，边表示两城之间的道路，边上权值可表示两城镇间的距离，交通费用或途中所需的时间等。
以上提出的问题就是带权图中求最短路径的问题，即求两个顶点间长度最短的路径。
最短路径问题的提法很多。在这里仅讨论单源最短路径问题：即已知有向图(带权)，我们希望找出从某个源点S∈V到G中其余各顶点的最短路径。
例如：下图(有向图G14)，假定以v1为源点，则其它各顶点的最短路径如下表所示：
图 G14
从有向图可看出，顶点v1到v4的路径有3条：(v1,v2,v4)，(v1,v4)，(v1,v3,v2,v4 )，其路径长度分别为：15,20和10。因此v1到v4的最短路径为(v1,v3,v2,v4 )。
为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。
那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉(Dijkstra)提出按路径长度递增产生诸顶点的最短路径算法，称之为迪杰斯特拉算法。
迪杰斯特拉算法求最短路径的实现思想是：设有向图G=(V,E)，其中，V={1,2,…,n}，cost是表示G的邻接矩阵，cost[i][j] 表示有向边<i,j>的权。若不存在有向边<i,j>，则cost[i][j]的权为无穷大(这里取值为32767)。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v1为源点，集合S的初态只包含顶点v1。数组dist记录从源点到其他各顶点当前的最短距离，其初值为dist[i]=cost[v1][i]，i=2,…,n。从S之外的顶点集合V-S 中选出一个顶点w，使dist[w]的值最小。于是从源点到达w只通过S 中的顶点，把w加入集合S中调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的dist[v] 和dist[w]+cost[w][v]中选择较小的值作为新的dist[v]。重复上述过程，直到S中包含V中其余顶点的最短路径。
最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了从源点到 V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中path[i] 表示从源点到顶点i之间的最短路径的前驱顶点。
⑷ 求如下有向图的关键路径以及任意两点之间的最短距离
用CPM算法求有向图的关键路径和用Dijkstra算法求有向图的最短路径的C语言程序如下
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#define MAX 20
#define INF 32767 // 此处修改最大值
#define nLENGTH(a) (sizeof(a)/sizeof(a[0]))
#define eLENGTH(a) (sizeof(a)/sizeof(char))/(sizeof(a[0])/sizeof(char))
typedef struct _graph{
char vexs[MAX]; // 顶点集合
int vexnum; // 顶点数
int edgnum; // 边数
int matrix[MAX][MAX]; // 邻接矩阵
}Graph, *PGraph;
// 边的结构体
typedef struct _EdgeData{
char start; // 边的起点
char end; // 边的终点
int weight; // 边的权重
}EData;
//指向节点的位置
int point_node(PGraph g,char c){
for(int i=0;i<g->vexnum;i++){
if(g->vexs[i]==c){
return i;
}
}
return -1;
}
PGraph create_graph(int b[][3],char a[],int n,int e){
char c1,c2; //边的2个顶点
PGraph g; //矩阵
g=(PGraph)malloc(sizeof(Graph));
//memset()第一个参数 是地址，第二个参数是开辟空间的初始值，第三个参数是开辟空间的大小
memset(g, 0, sizeof(Graph));
printf("顶点个数: ");//顶点数
g->vexnum=n;
printf("%d ",g->vexnum);
printf("边个数: ");//边数
g->edgnum=e;
printf("%d ",g->edgnum);
//初始化顶点
for(int j=0;j<g->vexnum;j++){
g->vexs[j]=a[j];
}
for(int i=0;i<g->edgnum;i++){
int p1,p2;
c1=char(b[i][0]);
c2=char(b[i][1]);
p1=point_node(g, c1);
p2=point_node(g, c2);
if (p1==-1 || p2==-1){
printf("input error: invalid edge! ");
free(g);
continue;
}
g->matrix[p1][p2]=b[i][2];
}
for(int i=0;i<g->vexnum;i++){
for(int j=0;j<g->vexnum;j++){
if(g->matrix[i][j]==0)
g->matrix[i][j]=INF;
}
}
return g;
}
//关键路径的最短时间
//关键路径法（Critical Path Method，CPM）
void CPM_road(PGraph g){
int i,j;
int a[MAX]={0},b[MAX]={-10};
int max=0;//最长路径
for( i=0;i<g->vexnum;i++){//列数遍历
for( j=0;j<g->vexnum;j++){//行数遍历
//如果g->matrix[j][i]大于0，说明此顶点有前顶点，由前边的遍历可知，前顶点的最长路径a[j]，
//加上g->matrix[j][i]的路径就是当前a[i]的路径
if(g->matrix[j][i]!=INF && g->matrix[j][i]+a[j]>max){
max=g->matrix[j][i]+a[j];
a[i]=max;
}
}
max=0;
}
//显示最长路径
printf("第一个顶点到每一个顶点的最长路径:");
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("V%d ",i+1);
}
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("%d ",a[i]);
}
printf(" ");
printf("最后一个顶点到每个顶点的最长路径:");
for( i=g->vexnum-1;i>=0;i--){ //列数遍历
for( j=g->vexnum-1;j>=0;j--){ //行数遍历
//如果g->matrix[j][i]大于0，说明此顶点有前顶点，由前边的遍历可知，前顶点的最长路径a[j]，
//加上g->matrix[j][i]的路径就是当前a[i]的路径
if(g->matrix[i][j]!=INF && g->matrix[i][j]+b[j]>max){
max=g->matrix[i][j]+b[j];
b[i]=max;
}
}
max=0;
}
//显示最长路径
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("V%d ",i+1);
}
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("%d ",b[i]);
}
printf(" ");
printf("关键路径: ");
for(i=0;i<g->vexnum;i++){
if(a[i]==a[g->vexnum-1]-b[i]){
printf("V%c ",g->vexs[i]);
}
}
printf(" ");
}
void print_shortest_path(PGraph g,int* distance,int* path,int* used,int start,int end){
// 输出最短距离并打印最短路径
int i = 0, pre, inverse_path[g->vexnum];
char s1[3],s2[3];
sprintf(s1, "V%d", (start+1));
sprintf(s2, "V%d", (end+1));
printf("从%s顶点到%s顶点的最短距离: %d ", s1, s2, distance[end]);
inverse_path[i] = end;
pre = path[end];
if(pre == -1){
printf("没有通路! ");
}else{
while(pre != start){
inverse_path[++i] = pre;
pre = path[pre];
}
inverse_path[++i] = start;
printf("从%s顶点到%s顶点的最短路径: ", s1, s2);
for(; i > 0; i--){
sprintf(s1, "V%d", (inverse_path[i]+1));
printf("%s -> ", s1);
}
sprintf(s1, "V%d", (inverse_path[i]+1));
printf("%s ", s1);
}
return;
}
void shortest_path(PGraph g,int start, int end){ // 基于Dijkstra算法的最短路径函数
int distance[g->vexnum]; // 用于存放起始点到其余各点的最短距离
int path[g->vexnum]; // 用于存放起始点到其余各点最短路径的前一个顶点
int used[g->vexnum] = { 0 }; // 用于标记该顶点是否已经找到最短路径
int i, j, min_node, min_dis, pass_flag = 0;
for(i = 0; i < g->vexnum; i++){
distance[i] = g->matrix[start][i]; // 初始化距离数组
if(g->matrix[start][i] < INF){
path[i] = start; // 初始化路径数组
}else{
path[i] = -1;
}
}
used[start] = 1;
path[start] = start;
for(i = 0; i < g->vexnum; i++){
min_dis = INF;
for(j = 0; j < g->vexnum; j++){
if(used[j] == 0 && distance[j] < min_dis){
min_node = j;
min_dis = distance[j];
pass_flag++; // 标记是否存在通路
}
}
if(pass_flag != 0){
used[min_node] = 1;
for(j = 0; j < g->vexnum; j++){
if(used[j] == 0){
if(g->matrix[min_node][j] < INF && distance[min_node] + g->matrix[min_node][j] < distance[j]){
distance[j] = distance[min_node] + g->matrix[min_node][j];
path[j] = min_node;
}
}
}
}
}
print_shortest_path(g,distance, path, used, start, end);
return;
}
int main(){
int i,j;
PGraph gp;
char a[]={'1', '2', '3', '4', '5', '6', '7'};
int b[][3]={{'1', '2',3},
{'1', '3',2},
{'1', '4',6},
{'2', '4',2},
{'2', '5',4},
{'3', '4',1},
{'3', '6',3},
{'4', '5',1},
{'5', '7',3},
{'6', '7',4}};
int n=nLENGTH(a);
int e=eLENGTH(b);
gp=create_graph(b,a,n,e);
//打印邻接矩阵
printf("邻接矩阵: ");
for (i = 0; i < gp->vexnum; i++){
for (j = 0; j < gp->vexnum; j++)
printf("%d ", gp->matrix[j][i]);
printf(" ");
}
CPM_road(gp);
printf(" ");
for(i=0;i<gp->vexnum;i++){
for(j=0;j<gp->vexnum;j++){
if(i!=j)
shortest_path(gp,i, j);
}
}
return 0;
}
运行结果
⑸ 用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，并写出执行算法过程中各步的状态。
迪克斯加（Dijkstra）算法(最短路径算法)是由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中任意两个顶点之间的最短路径问题。
举例来说，如果图中的顶点表示城市，而边上的权重表示着城市间开车行经的距离。 迪科斯彻算法可以用来找到两个城市之间的最短路径。
迪科斯彻算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。 每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 我们以E所有边的集合，而边的权重则由权重函数w: E → [0, ∞]定义。 因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想象成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。 已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径
这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时，源点s的路径长度值被赋为0（d[s]=0）， 同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d[v]= ∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到v的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到u的路径。这条路径的长度是d+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d达到它最终的值的时候每条边(u,v)都只被拓展一次。
算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。program dijkstra;
var
state:array[1..100]of boolean;
data:array[1..100,1..100]of longint;
n,i,j,k,min,node:longint;
begin
assign(input,'dijkstra.in');
assign(output,'dijkstra.out');
reset(input);
rewrite(output);
fillchar(data, sizeof(data), 0);
fillchar(state,sizeof(state),0);
readln(n);
for i:=1 to n do
for j:=1 to n do
begin
read(data[i,j]);
if data[i,j]=0 then data[i,j]:=maxint;
end;
state[1]:=true;
for k:=2 to n do
begin
min:=maxint;
{查找权值最小的点为node}
node:=1;
for i:=2 to n do
if (data[1,i]<min)and(state[i]=false) then
begin
min:=data[1,i];
node:=i;
end;
{更新其他各点的权值}
state[node]:=true;
for j:=1 to n do
if (data[1,node]+data[node,j]<data[1,j]) and (state[j]=false) then
data[1,j]:=data[1,node]+data[node,j];
end;
for i:=1 to n-1 do
if data[1,i]<>maxint then
write(data[1,i],' ')
else
write(-1,' ');
writeln(data[1,n]);
close(input);
close(output);
end.