有向图最短路径算法

❶ ArcGIS Engine10.2中的最短路径算法是什么算法有相关C#代码吗

最短路径算法——Dijkstra算法，又称为单源最短路径，所谓单源是在一个有向图中，从一个顶点出发，求该顶点至所有可到达顶点的最短路径问题。要顺利实现算法，要求理解Dijstra的算法，同时还要理解图的一些基本概念，图由节点和边构成，将节点和边看成对象，每个对象有自己的特有属性，如在GIS中，一个节点必须都有ID，横坐标，纵坐标等基本属性，边有起点节点，终点节点，长度等属性，而最短路径分析，就是根据边的长度(权值)进行分析的。

❷ 求有向图两个顶点间的最短路径的方法，用简单语言或举例描述。

在交通网络中，常常会提出许多这样的问题：两地之间是否有路相通？在有多条通路的情况下，哪一条最近？哪一条花费最少等。交通网络可以用带权图表示，图中顶点表示域镇，边表示两城之间的道路，边上权值可表示两城镇间的距离，交通费用或途中所需的时间等。
以上提出的问题就是带权图中求最短路径的问题，即求两个顶点间长度最短的路径。
最短路径问题的提法很多。在这里仅讨论单源最短路径问题：即已知有向图(带权)，我们希望找出从某个源点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*算法、 SPFA 算法、 Bellman-Ford 算法和 Floyd-Warshall 算法， 本文主要介绍其中的三种。 最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两 结点之间的最短路径。 算法具体的形式包括： 确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的 问题。 在无向图中该问题与确定起点的问题完全等同， 在有向图中该问题等同于把所有路径 方向反转的确定起点的问题。 确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。 全局最短路径问题：求图中所有的最短路径。 Floyd 求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度 O(V^3)。 Floyd-Warshall 算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法， 可以正确处理有向图或负权的最短路径问题。 Floyd-Warshall 算法的时间复杂度为 O(N^3)，空间复杂度为 O(N^2)。 Floyd-Warshall 的原理是动态规划： 设 Di,j,k 为从 i 到 j 的只以(1..k)集合中的节点为中间节点的最短路径的长度。 若最短路径经过点 k，则 Di,j,k = Di,k,k-1 + Dk,j,k-1； 若最短路径不经过点 k，则 Di,j,k = Di,j,k-1。 因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。 在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。 Floyd-Warshall 算法的描述如下： 1.for k ← 1 to n do 2.for i ← 1 to n do 3.for j ← 1 to n do 4.if (Di,k + Dk,j<Di,j) then 5.Di,j ← Di,k + Dk,j; 其中 Di,j 表示由点 i 到点 j 的代价，当 Di,j 为∞表示两点之间没有任何连接。 Dijkstra 求单源、无负权的最短路。时效性较好，时间复杂度为 O（V*V+E） 。 源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV） 。 当是稀疏图的情况时，此时 E=V*V/lgV，所以算法的时间复杂度可为 O（V^2） 。若是斐波那 契堆作优先队列的话，算法时间复杂度，则为 O（V*lgV + E） 。 Bellman-Ford 求单源最短路，可以判断有无负权回路（若有，则不存在最短路） ，时效性较好，时间复杂 度 O（VE） 。 Bellman-Ford 算法是求解单源最短路径问题的一种算法。 单源点的最短路径问题是指：给定一个加权有向图 G 和源点 s，对于图 G 中的任意一点 v， 求从 s 到 v 的最短路径。 与 Dijkstra 算法不同的是，在 Bellman-Ford 算法中，边的权值可以为负数。设想从我们可以 从图中找到一个环路（即从 v 出发，经过若干个点之后又回到 v）且这个环路中所有边的权 值之和为负。那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处 理这个负环路，程序就会永远运行下去。而 Bellman-Ford 算法具有分辨这种负环路的能力。 SPFA是 Bellman-Ford 的队列优化，时效性相对好，时间复杂度 O（kE）（k<<V） 。 。 与 Bellman-ford 算法类似， SPFA 算法采用一系列的松弛操作以得到从某一个节点出发到达图 中其它所有节点的最短路径。所不同的是，SPFA 算法通过维护一个队列，使得一个节点的 当前最短路径被更新之后没有必要立刻去更新其他的节点， 从而大大减少了重复的操作次数。 SPFA 算法可以用于存在负数边权的图，这与 dijkstra 算法是不同的。 与 Dijkstra 算法与 Bellman-ford 算法都不同，SPFA 的算法时间效率是不稳定的，即它对于不 同的图所需要的时间有很大的差别。 在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度 仅为 O(E)。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)次，此时算法退化为 Bellman-ford 算法，其时间复杂度为 O(VE)。 SPFA 算法在负边权图上可以完全取代 Bellman-ford 算法， 另外在稀疏图中也表现良好。 但是 在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的 Dijkstra 算法，以及 它的使用堆优化的版本。通常的 SPFA 算法在一类网格图中的表现不尽如人意。 

❺ dijkstra算法是什么

Dijkstra算法是由荷兰计算机科学家狄克斯特拉（Dijkstra）于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。

其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。

不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。

举例来说，如果图中的顶点表示城市，而边上的权重表示着城市间开车行经的距离。Dijkstra算法可以用来找到两个城市之间的最短路径。

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到任何其他顶点的最短路径。

❻ 求有向图最短路径算法（权重可为负）

单元最短路径：
1.如果没有负权环的稀疏图，可以用SPFA，时间复杂度O（KM）
M是边数，K是平均入队列的次数
2.如果没有负权环的稠密图，建议用Dijkstra O（N^2），用二叉堆可优化到
O（NlogN），斐波那契堆编程复杂度太高，不易于实现
3.如果有负权环，可以尝试floyd,O(n^3)

任两点最短路径：floyd较好实现，基于重标号johnson也不错（稀疏图效率高）
具体程序可以上网查

❼ 有向图求顶点出入度和最短路径Dijksatra算法。运行的出入度和求最短距离都有问题，请问出错在哪里

错在2处，一个图的初始化上，边的初始值应该是无穷INF

G.edges[i][j]=0;改成G.edges[i][j]=INF;

另外一个是函数outG显示邻接矩阵里，如果是INF则显示∞

❽ 用java怎么用迪杰斯特拉算有向图有权值的最短路径

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式
用OPEN,CLOSE表的方式，其采用的是贪心法的算法策略，大概过程如下：
1.声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点
2.初始阶段，将初始节点放入close，其他所有节点放入open
3.以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入close并从新计算路径，直至close包含所有子节点

代码实例如下：
Node对象用于封装节点信息，包括名字和子节点
[java] view plain
public class Node {
private String name;
private Map<Node,Integer> child=new HashMap<Node,Integer>();
public Node(String name){
this.name=name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Map<Node, Integer> getChild() {
return child;
}
public void setChild(Map<Node, Integer> child) {
this.child = child;
}
}

MapBuilder用于初始化数据源，返回图的起始节点
[java] view plain
public class MapBuilder {
public Node build(Set<Node> open, Set<Node> close){
Node nodeA=new Node("A");
Node nodeB=new Node("B");
Node nodeC=new Node("C");
Node nodeD=new Node("D");
Node nodeE=new Node("E");
Node nodeF=new Node("F");
Node nodeG=new Node("G");
Node nodeH=new Node("H");
nodeA.getChild().put(nodeB, 1);
nodeA.getChild().put(nodeC, 1);
nodeA.getChild().put(nodeD, 4);
nodeA.getChild().put(nodeG, 5);
nodeA.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeA, 1);
nodeB.getChild().put(nodeF, 2);
nodeB.getChild().put(nodeH, 4);
nodeC.getChild().put(nodeA, 1);
nodeC.getChild().put(nodeG, 3);
nodeD.getChild().put(nodeA, 4);
nodeD.getChild().put(nodeE, 1);
nodeE.getChild().put(nodeD, 1);
nodeE.getChild().put(nodeF, 1);
nodeF.getChild().put(nodeE, 1);
nodeF.getChild().put(nodeB, 2);
nodeF.getChild().put(nodeA, 2);
nodeG.getChild().put(nodeC, 3);
nodeG.getChild().put(nodeA, 5);
nodeG.getChild().put(nodeH, 1);
nodeH.getChild().put(nodeB, 4);
nodeH.getChild().put(nodeG, 1);
open.add(nodeB);
open.add(nodeC);
open.add(nodeD);
open.add(nodeE);
open.add(nodeF);
open.add(nodeG);
open.add(nodeH);
close.add(nodeA);
return nodeA;
}
}
图的结构如下图所示：

Dijkstra对象用于计算起始节点到所有其他节点的最短路径
[java] view plain
public class Dijkstra {
Set<Node> open=new HashSet<Node>();
Set<Node> close=new HashSet<Node>();
Map<String,Integer> path=new HashMap<String,Integer>();//封装路径距离
Map<String,String> pathInfo=new HashMap<String,String>();//封装路径信息
public Node init(){
//初始路径,因没有A->E这条路径,所以path(E)设置为Integer.MAX_VALUE
path.put("B", 1);
pathInfo.put("B", "A->B");
path.put("C", 1);
pathInfo.put("C", "A->C");
path.put("D", 4);
pathInfo.put("D", "A->D");
path.put("E", Integer.MAX_VALUE);
pathInfo.put("E", "A");
path.put("F", 2);
pathInfo.put("F", "A->F");
path.put("G", 5);
pathInfo.put("G", "A->G");
path.put("H", Integer.MAX_VALUE);
pathInfo.put("H", "A");
//将初始节点放入close,其他节点放入open
Node start=new MapBuilder().build(open,close);
return start;
}
public void computePath(Node start){
Node nearest=getShortestPath(start);//取距离start节点最近的子节点,放入close
if(nearest==null){
return;
}
close.add(nearest);
open.remove(nearest);
Map<Node,Integer> childs=nearest.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){//如果子节点在open中
Integer newCompute=path.get(nearest.getName())+childs.get(child);
if(path.get(child.getName())>newCompute){//之前设置的距离大于新计算出来的距离
path.put(child.getName(), newCompute);
pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"->"+child.getName());
}
}
}
computePath(start);//重复执行自己,确保所有子节点被遍历
computePath(nearest);//向外一层层递归,直至所有顶点被遍历
}
public void printPathInfo(){
Set<Map.Entry<String, String>> pathInfos=pathInfo.entrySet();
for(Map.Entry<String, String> pathInfo:pathInfos){
System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());
}
}
/**
* 获取与node最近的子节点
*/
private Node getShortestPath(Node node){
Node res=null;
int minDis=Integer.MAX_VALUE;
Map<Node,Integer> childs=node.getChild();
for(Node child:childs.keySet()){
if(open.contains(child)){
int distance=childs.get(child);
if(distance<minDis){
minDis=distance;
res=child;
}
}
}
return res;
}
}

Main用于测试Dijkstra对象
[java] view plain
public class Main {
public static void main(String[] args) {
Dijkstra test=new Dijkstra();
Node start=test.init();
test.computePath(start);
test.printPathInfo();
}
}

❾ 权图中求最短路径都有哪些算法

带权图也分有向和无向两种，基本的算法可以看看书咯。
带权的无向图的最短路径又叫最小生成树，Prim算法和Kruskal算法；
带权的有向图的最短路径算法有迪杰斯特拉算法和佛洛依德算法；

❿ matlab有向图指定两点间最短路径算法，最好可以转换为距离矩阵更好

function preorder($root)
configure:3438: $? = 0
configure:3427: gcc -v >&5
Using built-in specs.
Target: i686-apple-darwin11
Configured with: /private/var/tmp/llvmgcc42/llvmgcc42-2336.11~182/src/configure --disable-checking --enable-werror --prefix=/Applications/Xcode.app/Contents/Developer/usr/llvm-gcc-4.2 --mandir=/share/man --enable-languages