路径算法
Ⅰ 求一个最优路径算法的思路
同意楼上，最长路径是NPC问题，不存在多项式算法。
证明是简单的：
1、最长无环路问题的判定版本是“给定有向图D和整数k，问D中是否存在长度大于或等于k的无环路”（这一表述对有权图和无权图都有效）。
2、将Hamilton路问题规约到最长无环路问题（的判定版本）是显然的：输入一个n顶点的有向图D，直接问：有向图D中是否存在长度大于等于n-1的无环路？
简言之，对任意n顶点的有向图D，假如能够D中的找到最长无环路P，那么就能立即知道D中是否存在Hamilton路（只需看P的长度是否为n-1即可），从而最长无环路问题是NPC。
小规模就直接DFS吧。大规模的时候DFS剪枝。不过确实不好做呀。
有向无圈图的话可以用dijstra贪心，或者简单用folyed算法就可以了（把最小化变为最大化）。
有圈的话您……或者能缩圈么？可以考虑。总之比较复杂。
Ⅱ 图论中，求欧拉路径的算法有哪些
首先要根据欧拉路径的存在条件来判断一个图是否存在欧拉路径,判断条件为如下3条
对于一个无向图，如果它每个点的度都是偶数，那么它存在一条欧拉回路；
如果有且仅有2个点的度为奇数，那么它存在一条欧拉路；
如果超过2个点的度为奇数，那么它就不存在欧拉路了。
然后可以用Fleury算法求欧拉路径,可以参照
http://www.cnblogs.com/Lyush/archive/2013/04/22/3036659.html
Ⅲ 关键路径算法的时间复杂度
所谓关键路径，就是从工程开始到工程结束所用时间最长的路径。这是因为，在途中的每一个阶段开始之前，都要保证此前的准备工作都已完成，要不然后续工程会无法完成，在寻找路径时，只能一条路径一条路径的比较。本题结果是
Ⅳ 求最优路径的算法
以下是C写的广度优先的最短路径穷举法,希望对你有所帮助.
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
#define SIGHTS 4 //自定义景点个数为4，以后可以扩充
class Sight //景点类信息，以后可以扩充
{
public:
Sight(string name, string sd) { sname = name; sight_detial = sd; }
string Sight_Name() { return sname; }
string Sight_detial() { return sight_detial; }
protected:
string sname; //景点名称
string sight_detial; //景点备注
};
struct SI
{
string sname; //景点名称
int index; //景点编码
};
SI SightInfo[SIGHTS];
map<int, string>results; //距离与路径的映射结构体，可以动态扩充
vector<Sight> sights; //VECTOR向量保存景点信息，目前的作用只是保存
//但是其强大的功能完全可以应付以后的功能扩充
int MinDistanct = 50000; //假定最小距离为一个很大的值
string Sight_Names = "枫林园蛟桥园青山园麦庐园 "; //目标字符串
string Best_Path; //保存最佳路径的STRING字符串
int DISTANCE[4][4] = { //查找表，用于储存接点之间距离的信息
0, 1500, 2500, 2400,
1500, 0, 800, 0,
2500, 800, 0, 200,
2400, 0, 200, 0
};
bool connect[4][4] = { //查找表，用于储存接点之间连通的信息
0, 1, 1, 1,
1, 0, 1, 0,
1, 1, 0, 1,
1, 0, 1, 0
};
void InitSights()
{ //初始化景点的各类信息
SightInfo[0].index=0;
SightInfo[0].sname = "麦庐园";
SightInfo[1].index=1;
SightInfo[1].sname = "枫林园";
SightInfo[2].index=2;
SightInfo[2].sname = "蛟桥园";
SightInfo[3].index=3;
SightInfo[3].sname = "青山园";
Sight s1("枫林园",
"枫林园以计算机系的理工科学生为主，是江西财经大学的唯一一个计算机学院");
sights.push_back(s1);
Sight s2("蛟桥园",
"蛟桥园是江西财经大学的会计、贸易等财务教学为主的教学楼群，为本部");
sights.push_back(s2);
Sight s3("青山园",
"青山园是江西财经大学的会计、贸易等财务教学为主的学生的宿舍群");
sights.push_back(s3);
Sight s4("麦庐园",
"麦庐园是江西财经大学的外语、艺术等人文科学为主的学习园地");
sights.push_back(s4);
}
void Find_Ways(string start, string end, int DIST, string path, int depth)
{ //递归调用，逐层寻找可连通的路径，并以该路径继续重复循环查找，根据分析可以
//知道，所有最优解即最短路径所经过的接点数目必定小于N，于是采用广度优先遍历，
//设置count为循环深度，当count大于SIGHTS时退出循环
int count = 1;
int i,j;
int start1 = 0,end1 = 0;
int distanct = 0, storeDist = 0;
string temp, target, pathway, storePath; //临时储存体，用于恢复递归调用后会
//改变的数据，以便之后无差别使用
count += depth;
if(count > SIGHTS)
return;
distanct += DIST; //距离累加
if(path=="") //第一次时，pathway初始化为第一个接点名称
{
pathway = start;
pathway += "=>";
}
if(path!="")
pathway = path;
storeDist = distanct; //填充临时储存值
storePath = pathway;
for(i = 0; i < SIGHTS; ++i) //通过遍历，查找景点名称对应的编号
{
if(start == SightInfo[i].sname)
start1 = SightInfo[i].index;
if(end == SightInfo[i].sname)
end1 = SightInfo[i].index;
}
for(i = 0; i < SIGHTS; i++) //算法核心步骤
{
if(connect[start1][i] != 0)
{
if(i==end1) //如果找到了一条路径，则保存之
{
distanct += DISTANCE[start1][end1];
for(j = 0; j < SIGHTS; ++j)
{
if(end1==SightInfo[j].index)
target = SightInfo[j].sname;
}
pathway += target;
results.insert(make_pair(distanct, pathway)); //保存结果路径信息
distanct = storeDist; //恢复数据供下次使用
pathway = storePath;
}
else //分支路径
{
for(j = 0; j < SIGHTS; ++j)
{
if(i==SightInfo[j].index)
temp = SightInfo[j].sname;
}
pathway += temp;
pathway += "=>";
distanct += DISTANCE[start1][i];
Find_Ways(temp, end, distanct, pathway, count); //以该连通的分支
//路径继续递归调用，查找子层路径信息。
distanct = storeDist; //恢复数据
pathway = storePath;
}
}
}
}
void Find_Best_Way()
{ //该函数建立在上述函数执行完毕之后，在map映射结构中通过对比每条路径的长度，来
//选择最优解
map<int, string>::iterator itor = results.begin();
while(itor!=results.end()) //寻找最小值
{
// cout<<"distanct = "<<itor->first<<endl;
if(itor->first < MinDistanct)
MinDistanct = itor->first;
itor++;
}
itor = results.begin();
while(itor!=results.end()) //寻找最小值所对应的整个路径字符串
{
if(itor->first == MinDistanct)
Best_Path = itor->second;
itor++;
}
}
int main(int argc, char *argv[])
{
int choice;
size_t t1=0,t2=0;
string source, termination;
InitSights();
do{
cout<<"////////////////////////////////////////////////////////\n"
<<"**** 请输入您所需要的服务号码: ********\n"
<<"**** 1.枫林园介绍 ********\n"
<<"**** 2.蛟桥园介绍 ********\n"
<<"**** 3.青山园介绍 ********\n"
<<"**** 4.麦庐园介绍 ********\n"
<<"**** 5.查询地图路径 ********\n"
<<"**** 6.退出查询系统 ********\n"
<<"////////////////////////////////////////////////////////\n"
<<endl;
cin>>choice;
switch(choice)
{
case 1:
cout<<sights[0].Sight_Name()<<endl
<<sights[0].Sight_detial()<<endl;
break;
case 2:
cout<<sights[1].Sight_Name()<<endl
<<sights[1].Sight_detial()<<endl;
break;
case 3:
cout<<sights[2].Sight_Name()<<endl
<<sights[2].Sight_detial()<<endl;
break;
case 4:
cout<<sights[3].Sight_Name()<<endl
<<sights[3].Sight_detial()<<endl;
break;
case 5:
flag1:
cout<<"请输入路径的起点"<<endl;
cin>>source;
cout<<"请输入路径的终点"<<endl;
cin>>termination;
if((t1=Sight_Names.find(source,t1))==string::npos || (t2=Sight_Names.find(termination,t2))==string::npos)
{ //检查输入的数据是否含有非法字符
cerr<<"输入的路径结点不存在，请重新输入:"<<endl;
goto flag1;
}
Find_Ways(source, termination, 0, "",0); //寻找所有可能解
Find_Best_Way(); //在所有可能解中找到最优解
cout<<"最佳路径是："<< Best_Path <<endl
<<"最小路程为(米):"<< MinDistanct<<endl;
t1 = 0; //恢复字符串下标，以支持下次查询
t2 = 0;
break;
case 6:
break;
default:
cerr<<"您的选择超出了范围，请重新输入:"<<endl;
break;
}
}while(choice!=6);
system("pause");
return 0;
}
Ⅳ 求路径算法
到达每个点之前只可能在左右下相邻的点，因此只要把左右下的最短路径的距离加上到达当前点的边的距离，保留个最小的就可以了，所以说思路和经典最短路径一样。（属于动态规划算法，这是经典的算法设计思想）
关键是算的顺序。对于只允许向上向右的情况，先算哪个都行，只要保证算之前左边和下边节点之前算过吧并且是正确的就行。
最下边第一层最好算，和只能向右上的情况一样。
之后一层一层地算就可以，因为多出来向左走并不会影响下面的层计算出来的最短路径。
关键是同层是怎么算，应该从左向右算。
PS：上面的算法只是对网格的一个特例，可以一般化。
PSS：如果对算法感兴趣，推荐《算法导论》，只要理解力足够，基本不需要事先学微积分之类的课。总之，推荐！但考虑到你会提出这样的问题，直接无视吧。
Ⅵ 求有向图两点间是否存在路径的“算法思想”
从一个点进行深度优先搜索 看能不能到另外一个点
Ⅶ 一个矩阵从一点到另外一点的所有路径的算法
我去ebay面试的题目 和LZ有点区别 从（0,0）到（3,3） 只能往上和往右走 求所有路径
回家做了一个小时 用java做的
不能用递归 如果矩阵大了 递归会栈溢出
如果是这个题目 回去给你发代码
Ⅷ 百度地图的路径搜索算法
这个还是要问程序猿，现在比较流行A*算法，至于网络是否开发出了新的算法不得而知，毕竟没有完全相同的程序。
给你看一篇文献：
地图中最短路径的搜索算法研究
学生:李小坤 导师：董峦
摘要：目前为止, 国内外大量专家学者对“最短路径问题”进行了深入的研究。本文通过理论分析, 结合实际应用，从各个方面较系统的比较广度优先搜索算法(BFS)、深度优先搜索算法(DFS)、A* 算法的优缺点。
关键词:最短路径算法；广度优先算法；深度优先算法；A*算法；
The shortest path of map's search algorithm
Abstract:So far, a large number of domestic and foreign experts and scholars on the" shortest path problem" in-depth study. In this paper, through theoretical analysis and practical application, comprise with the breadth-first search algorithm ( BFS ), depth-first search algorithm ( DFS ) and the A * algorithms from any aspects of systematic.
Key words: shortest path algorithm; breadth-first algorithm; algorithm; A * algorithm;
前言：
最短路径问题是地理信息系统（GIS）网络分析的重要内容之一，而且在图论中也有着重要的意义。实际生活中许多问题都与“最短路径问题”有关, 比如: 网络路由选择, 集成电路设计、布线问题、电子导航、交通旅游等。本文应用深度优先算法，广度优先算法和A*算法，对一具体问题进行讨论和分析，比较三种算的的优缺点。
在地图中最短路径的搜索算法研究中，每种算法的优劣的比较原则主要遵循以下三点:[1]
(1)算法的完全性：提出一个问题，该问题存在答案，该算法能够保证找到相应的答案。算法的完全性强是算法性能优秀的指标之一。
(2)算法的时间复杂性: 提出一个问题，该算法需要多长时间可以找到相应的答案。算法速度的快慢是算法优劣的重要体现。
(3)算法的空间复杂性:算法在执行搜索问题答案的同时，需要多少存储空间。算法占用资源越少，算法的性能越好。
地图中最短路径的搜索算法:
1、广度优先算法
广度优先算法(Breadth-First-Search)，又称作宽度优先搜索，或横向优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型,Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。广度优先算法其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。
广度优先搜索算法伪代码如下：[2-3]
BFS(v)//广度优先搜索G，从顶点v开始执行
//所有已搜索的顶点i都标记为Visited(i)=1.
//Visited的初始分量值全为0
Visited(v)=1;
Q=[];//将Q初始化为只含有一个元素v的队列
while Q not null do
u=DelHead(Q);
for 邻接于u的所有顶点w do
if Visited(w)=0 then
AddQ(w,Q); //将w放于队列Q之尾
Visited(w)=1;
endif
endfor
endwhile
end BFS
这里调用了两个函数：AddQ(w,Q)是将w放于队列Q之尾；DelHead(Q)是从队列Q取第一个顶点，并将其从Q中删除。重复DelHead(Q)过程，直到队列Q空为止。
完全性：广度优先搜索算法具有完全性。这意指无论图形的种类如何，只要目标存在，则BFS一定会找到。然而，若目标不存在，且图为无限大，则BFS将不收敛（不会结束）。
时间复杂度：最差情形下，BFS必须寻找所有到可能节点的所有路径，因此其时间复杂度为,其中|V|是节点的数目，而 |E| 是图中边的数目。
空间复杂度：因为所有节点都必须被储存，因此BFS的空间复杂度为，其中|V|是节点的数目，而|E|是图中边的数目。另一种说法称BFS的空间复杂度为O(B),其中B是最大分支系数，而M是树的最长路径长度。由于对空间的大量需求，因此BFS并不适合解非常大的问题。[4-5]
2、深度优先算法
深度优先搜索算法（Depth First Search）英文缩写为DFS，属于一种回溯算法，正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。[6]其过程简要来说是沿着顶点的邻点一直搜索下去，直到当前被搜索的顶点不再有未被访问的邻点为止，此时，从当前辈搜索的顶点原路返回到在它之前被搜索的访问的顶点，并以此顶点作为当前被搜索顶点。继续这样的过程，直至不能执行为止。
深度优先搜索算法的伪代码如下：[7]
DFS(v) //访问由v到达的所有顶点
Visited(v)=1;
for邻接于v的每个顶点w do
if Visited(w)=0 then
DFS(w);
endif
endfor
end DFS
作为搜索算法的一种，DFS对于寻找一个解的NP（包括NPC）问题作用很大。但是，搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法，它的效率比较低，在数据规模变大时，这种算法就显得力不从心了。[8]关于深度优先搜索的效率问题，有多种解决方法。最具有通用性的是剪枝，也就是去除没有用的搜索分支。有可行性剪枝和最优性剪枝两种。
BFS:对于解决最短或最少问题特别有效，而且寻找深度小，但缺点是内存耗费量大（需要开大量的数组单元用来存储状态）。
DFS：对于解决遍历和求所有问题有效，对于问题搜索深度小的时候处理速度迅速，然而在深度很大的情况下效率不高。
3、A*算法
1968年的一篇论文，“P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107, 1968”。[9]从此，一种精巧、高效的算法——A*算法问世了，并在相关领域得到了广泛的应用。A* 算法其实是在宽度优先搜索的基础上引入了一个估价函数,每次并不是把所有可扩展的结点展开,而是利用估价函数对所有未展开的结点进行估价, 从而找出最应该被展开的结点,将其展开,直到找到目标节点为止。
A*算法主要搜索过程伪代码如下：[10]
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
算起点的估价值;
将起点放入OPEN表;
while(OPEN!=NULL) //从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
endif
for(当前节点n 的每个子节点X)
算X的估价值;
if(X in OPEN)
if(X的估价值小于OPEN表的估价值)
把n设置为X的父亲;
更新OPEN表中的估价值; //取最小路径的估价值;
endif
endif
if(X inCLOSE)
if( X的估价值小于CLOSE表的估价值)
把n设置为X的父亲;
更新CLOSE表中的估价值;
把X节点放入OPEN //取最小路径的估价值
endif
endif
if(X not inboth)
把n设置为X的父亲;
求X的估价值;
并将X插入OPEN表中; //还没有排序
endif
end for
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
end while(OPEN!=NULL)
保存路径，即 从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；
A *算法分析：
DFS和BFS在展开子结点时均属于盲目型搜索，也就是说，它不会选择哪个结点在下一次搜索中更优而去跳转到该结点进行下一步的搜索。在运气不好的情形中，均需要试探完整个解集空间, 显然，只能适用于问题规模不大的搜索问题中。而A*算法与DFS和BFS这类盲目型搜索最大的不同，就在于当前搜索结点往下选择下一步结点时，可以通过一个启发函数来进行选择，选择代价最少的结点作为下一步搜索结点而跳转其上。[11]A *算法就是利用对问题的了解和对问题求解过程的了解, 寻求某种有利于问题求解的启发信息, 从而利用这些启发信息去搜索最优路径.它不用遍历整个地图, 而是每一步搜索都根据启发函数朝着某个方向搜索.当地图很大很复杂时, 它的计算复杂度大大优于D ijks tr a算法, 是一种搜索速度非常快、效率非常高的算法.但是, 相应的A*算法也有它的缺点.启发性信息是人为加入的, 有很大的主观性, 直接取决于操作者的经验, 对于不同的情形要用不同的启发信息和启发函数, 且他们的选取难度比较大,很大程度上找不到最优路径。
总结：
本文描述了最短路径算法的一些步骤，总结了每个算法的一些优缺点，以及算法之间的一些关系。对于BFS还是DFS，它们虽然好用，但由于时间和空间的局限性，以至于它们只能解决规模不大的问题，而最短或最少问题应该选用BFS,遍历和求所有问题时候则应该选用DFS。至于A*算法，它是一种启发式搜索算法，也是一种最好优先的算法，它适合于小规模、大规模以及超大规模的问题，但启发式搜索算法具有很大的主观性，它的优劣取决于编程者的经验，以及选用的启发式函数，所以用A*算法编写一个优秀的程序，难度相应是比较大的。每种算法都有自己的优缺点，对于不同的问题选择合理的算法，才是最好的方法。
参考文献：
[1]陈圣群,滕忠坚,洪亲,陈清华.四种最短路径算法实例分析[J].电脑知识与技术(学术交流),2007(16):1030-1032
[2]刘树林,尹玉妹.图的最短路径算法及其在网络中的应用[J].软件导刊,2011(07):51-53
[3]刘文海,徐荣聪.几种最短路径的算法及比较[J].福建电脑，2008(02）:9-12
[4]邓春燕.两种最短路径算法的比较[J].电脑知识与技术，2008（12）：511-513
[5]王苏男,宋伟,姜文生.最短路径算法的比较[J].系统工程与电子技术,1994(05)：43-49
[6]徐凤生,李天志.所有最短路径的求解算法[J].计算机工程与科学,2006(12)：83-84
[7]李臣波,刘润涛.一种基于Dijkstra的最短路径算法[J].哈尔滨理工大学学报,2008(03)：35-37
[8]徐凤生.求最短路径的新算法[J].计算机工程与科学,2006(02).
[9] YanchunShen . An improved Graph-based Depth-First algorithm and Dijkstra algorithm program of police patrol [J] . 2010 International Conference on Electrical Engineering and Automatic Control , 2010(3) : 73-77
[10]部亚松.VC++实现基于Dijkstra算法的最短路径[J].科技信息(科学教研),2008(18)：36-37
[11] 杨长保,王开义,马生忠.一种最短路径分析优化算法的实现[J]. 吉林大学学报(信息科学版),2002(02)：70-74
Ⅸ C++ 算法，路径，多谢
仅供参考 了
#include "stdio.h"
#define maxver 10
#define maxright 100
int G[maxver][maxver],record=0,touched[maxver][maxver];
int circle=0;
int FindCircle(int,int,int,int);
int main()
{
int path[maxver][2],used[maxver][maxver];
int i=0,j=0,k=0,t,min=maxright,exsit=0;
int v1,v2,num,temp,status=0;
restart:
printf("Please enter the number of vertex(s) in the graph:\n");
scanf("%d",&num);
if (num>maxver||num<0)
{
printf("Error!Please reinput!\n");
goto restart;
}
for (j=0;j<num;j++)
for (k=0;k<num;k++)
{
if (j==k)
{
G[j][k]=maxright;
used[j][k]=1;
touched[j][k]=0;
}
else
if (j<k)
{
re:
printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1);
scanf("%d",&temp);
if (temp>=maxright||temp<-1)
{
printf("Invalid input!\n");
goto re;
}
if (temp==-1)
temp=maxright;
G[j][k]=G[k][j]=temp;
used[j][k]=used[k][j]=0;
touched[j][k]=touched[k][j]=0;
}
}
for (j=0;j<num;j++)
{
path[j][0]=0;
path[j][1]=0;
}
for (j=0;j<num;j++)
{
status=0;
for (k=0;k<num;k++)
if (G[j][k]<maxright)
{
status=1;
break;
}
if (status==0)
break;
}
for (i=0;i<num-1&&status;i++)
{
for (j=0;j<num;j++)
for (k=0;k<num;k++)
if (G[j][k]<min&&!used[j][k])
{
v1=j;
v2=k;
min=G[j][k];
}
if (!used[v1][v2])
{
used[v1][v2]=1;
used[v2][v1]=1;
touched[v1][v2]=1;
touched[v2][v1]=1;
path[0]=v1;
path[1]=v2;
for (t=0;t<record;t++)
FindCircle(path[t][0],path[t][0],num,path[t][0]);
if (circle)
{
/*if a circle exsits,roll back*/
circle=0;
i--;
exsit=0;
touched[v1][v2]=0;
touched[v2][v1]=0;
min=maxright;
}
else
{
record++;
min=maxright;
}
}
}
if (!status)
printf("We cannot deal with it because the graph is not connected!\n");
else
{ for (i=0;i<num-1;i++)
printf("Path %d:vertex %d to vertex %d\n",i+1,path[0]+1,path[1]+1);
}
return 1;
}
int FindCircle(int start,int begin,int times,int pre)
{
/* to judge whether a circle is proced*/
int i;
for (i=0;i<times;i++)
if (touched[begin]==1)
{
if (i==start&&pre!=start)
{
circle=1;
return 1;
break;
}
else
if (pre!=i)
FindCircle(start,i,times,begin);
else
continue;
}
return 1;
}
Ⅹ 路径分析的最优路径分析方法
1．道路预处理
进行道路数据录入时，往往在道路的交叉接合处出现重叠或相离的情况，不宜计算机处理。因此，需要对原始数据进行预处理，使道路接合符合处理要求。进行预处理时，取每条线段的首末节点坐标为圆心，以给定的阈值为半径作圆域，判断其他线段是否与圆域相交，如果相交，则相交的各个线对象共用一个节点号。
2．道路自动断链
对道路进行预处理之后即可获得比较理想的数据，在此基础上再进行道路的自动断链。步骤如下：
（1）取出所有线段记录数n，从第一条线段开始；
（2）找出所有与之相交的线段并求出交点数m；
（3）将m个交点和该线段节点在判断无重合后进行排序；
（4）根据交点数量，该线段被分成m+1段；
（5）第一段在原始位置不变，后m段从记录尾开始递增；
（6）重复（2）～（5），循环至n。
3．节点匹配
拓扑关系需使用统一的节点。节点匹配方法是按记录顺序将所有线段的始末点加上相应节点号，坐标相同的节点共用一个节点号，与前面所有线段首末点都不相同的节点按自然顺序递增1。
4．迪杰克斯特拉（Dijkstra）算法
经典的图论与计算机算法的有效结合，使得新的最短路径算法不断涌现。目前提出的最短路径算法中，使用最多、计算速度比较快，又比较适合于计算两点之间的最短路径问题的数学模型就是经典的Dijkstra算法。
该算法是典型的单源最短路径算法，由Dijkstra EW于1959年提出，适用于所有弧的权均为非负的情况，主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。该算法的基本思想是：认为两节点间最佳路径要么是直接相连，要么是通过其他已找到的与起始点的最佳路径的节点中转点。定出起始点P0后，定能找出一个与之直接相连且路径长度最短的节点，设为P1，P0到P1就是它们间的最佳路径。
Dijkstra算法的基本流程如下：首先将网络中所有节点分成两组，一组包含了已经确定属于最短路径中点的集合，记为S（该集合在初始状态只有一个源节点，以后每求得一条最短路径，就将其加入到集合S中，直到全部顶点都加入到S中，算法就结束了）；另一组是尚未确定最短路径的节点的集合，记为V，按照最短路径长度递增的次序依次把第二组的顶点加入到第一组中，在加入的过程中总保持从源点到S中各顶点的最短路径长度不大于从源点到V中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点距离就是从源点到此顶点的最短路径长度，V中的顶点距离是从源点到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
