[问题分析]
对于一个含有n个顶点和e条边的图来说，从某一个顶点Vi到其余任一顶点Vj的最短路径，可能是它们之间的边（Vi，Vj），也可能是经过k个中间顶点和k+1条边所形成的路径(1≤k≤n-2)。下面给出解决这个问题的Dijkstra算法思想。
设图G用邻接矩阵的方式存储在GA中，GA[i,j]=maxint表示Vi，Vj是不关联的，否则为权值（大于0的实数）。设集合S用来保存已求得最短路径的终点序号，初始时S=[Vi]表示只有源点，以后每求出一个终点Vj，就把它加入到集合中并作为新考虑的中间顶点。设数组dist[1..n]用来存储当前求得的最短路径，初始时Vi，Vj如果是关联的，则dist[j]等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，dist[j]可能越来越小。再设一个与dist对应的数组path[1..n]用来存放当前最短路径的边，初始时为Vi到Vj的边，如果不存在边则为空。
执行时，先从S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为dist[m]），该元素值就是从源点Vi到终点Vm的最短路径长度，对应的path[m]中的顶点或边的序列即为最短路径。接着把Vm并入集合S中，然后以Vm作为新考虑的中间顶点，对S以外的每个顶点Vj，比较dist[m]+GA[m,j]的dist[j]的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替dist[j]，同时把Vj或边（Vm，Vj）并入到path[j]中。重复以上过程n-2次，即可在dist数组中得到从源点到其余各终点的最段路径长度，对应的path数组中保存着相应的最段路径。
下面给出具体的Dijkstra算法框架（注：为了实现上的方便，用一个一维数组s[1..n]代替集合S，用来保存已求得最短路径的终点集合，即如果s[j]=0表示顶点Vj不在集合中，反之，s[j]=1表示顶点Vj已在集合中）。
Procedure Dijkstra(GA,dist,path,i)；
{表示求Vi到图G中其余顶点的最短路径，GA为图G的邻接矩阵，dist和path为变量型参数，
其中path的基类型为集合}
Begin
For j:=1 To n Do Begin {初始化}
If j<>i Then s[j]:=0 Else s[j]:=1；
dist[j]:=GA[i,j]；
If dist[j]<maxint Then path[j]:=[i]+[j] Else path[j]:=[ ]；
End；
For k:=1 To n-2 Do
Begin
w:=maxint；m:=i；
For j:=1 To n Do {求出第k个终点Vm}
If (s[j]=0) and (dist[j]<w) Then Begin m:=j；w:=dist[j]； End；
If m<>i Then s[m]:=1 else exit；
{若条件成立，则把Vm加入到S中，
否则退出循环，因为剩余的终点，其最短路径长度均为maxint，无需再计算下去}
For j:=1 To n Do {对s[j]=0的更优元素作必要修改}
If (s[j]=0) and (dist[m]+GA[m,j]<dist[j])
Then Begin Dist[j]:=dist[m]+GA[m,j]；path[j]:=path[m]+[j]；End；
End；
End；
（1）从一个顶点到其余各顶点的最短路径
对于一个含有n个顶点和e条边的图来说，从某个顶点vi到其余任一顶点vj的最短路径，可能是它们之间的边（vi，vj），也可能是经过k个中间点和k+1条边所形成的路径（1≤k ≤n-2）。
首先来分析Dijkstra的算法思想
设图G用邻接矩阵的方式存储在GA中，GA[I，j]=maxint表示vi，vj是不关联的，否则为权值（大于0的实数）。设集合S用来存储保存已求得最短路径的终点序号，初始时S=[vi]表示只有源点，以后每求出一个终点vj，就把它加入到集合中并作为新考虑的中间顶点。设数组dist[1..n]用来存储当前求得的最短路径，初始时vi，vj如果是关联的，则dist[j]等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，dist[j]可能越来越小。再设一个与dist对应的数组path[1..n]用来存放当前最短路径的边，初始时vi到vj的边，如果不存在边则为空。
执行时，先从S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为dist[m]），该元素值就是从源点vi到终点vm的最短路径长度，对应的path[m]中的顶点或边的序列即为最短路径。接着把vm并入集合S中，然后以vm作为新考虑的中间顶点，对S以外的每个顶点vj，比较dist[m]+GA[i，j]与dist[j]的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替dist[j]，同时把vj或边（vm，vj）并入到path[j]中。重复以上过程n-2次，即可在dist数组中得到从源点到其余个终点的最短路径长度，对应的path数组中保存着相应的最短路径。
为了实现上的方便，用一个一维数组s[1..n]代替集合s，用来保存已求得最短路径的终点集合，即如果s[j]=0表示顶点vj不在集合中，反之，s[j]表示顶点vj已在集合中）。
Procedure dijkstra (GA,dist path,I)
begin
for j:= 1 to n do begin
if j<>I then s[j]:=0;{j不在集合中} else s[j]:=1;{j在集合中}；
dist[j]:=GA[I,J];
IF dist [j]<maxint {maxint为假设的一个足够大的数}
Then path [j]:=[I]+[j]
Else path[j]:=[ ];
End;
For k:= 1 to n-1 do begin w:=maxint;m:=I;
For j:= 1 to n do{求出第k个终点Vm}
if (s[j]=0)and(dist[j]<w) then begin m:=j;w:=dist[j];end;
If m<>I then s[m]:=1 else exit;{若条件成立，则把Vm加入到s中，否则退出循环，因为
剩余的终点，其最短路径长度均为maxint，无需再计算下去}
for j:=1 to n do {对s[j]=0的更优元素作必要修改}
if (s[j]=0)and (dist[m]+GA[m,j]<dist[j])
then begin
dist[j]:=dist[m]+GA[m,j];
path[j]:=path[m]+[j];
End;
End;
End;
用集合的思想：
for k:=1 to n-1 do
begin
wm:=max;j:=0;
for i:=1 to n do
if not(i in s)and(dist[i]<wm) then begin j:=i;wm:=dist[i];end;
s:=s+[j];
for i:=1 to n do
if not(i in s)and(dist[j]+cost[j,i]<dist[i]) then
begin dist[i]:=dist[j]+cost[j,i];path[i]:=path[j]+char(48+i);end;
end;
Dijkstra算法是由荷兰计算机科学家 Edsger Wybe Dijkstra于1959年提出的单源点最短路径算法（SSSP:Single Souce Shortest Path）。是一个解决加权图（不含负权重的边）中从一个顶点到其余各个顶点最短路径问题的算法。Dijkstra算法是一个集 贪心算法 ， 广度优先搜索（BFS） 和 动态规划 于一身的最短路径算法。Dijkstra算法的主要特点是从起源点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接顶点，直到扩展到终点为止。
Dijkstra算法通过维护两个集合： (已求出最短路径的顶点)和 （未求出最短路径的顶点），每次迭代地从 中移除路径距离最小的点到集合 中，并通过这个新移入的点来更新 中各个顶点到源点的最短路径，直到集合 为空。下面我们通过一个例子来简单描述Dijkstra算法的过程。
假设我们有如下的图，其中顶点A未此次算法的起点：
首先我们需要初始化两个集合 和 ，以及 中每个顶点到源点的距离，若不直接于A相邻，结果置为正无穷∞。
Step 1： 从集合 中挑选出距离最小的点，这里会挑选出顶点F，集合 和 变更为： ， ，根据最新的 ，重新计算 中顶点到源点A的最短距离。
Step 2:： 从集合 中挑选出距离最小的点，这里会挑选出顶点E，集合 和 变更为： ， ，根据最新的 ，重新计算 中顶点到源点A的最短距离。
Step 3： 从集合 中挑选出距离最小的点，这里会挑选出顶点C，集合 和 变更为： ， ，根据最新的 ，重新计算 中顶点到源点A的最短距离。
Step 4： 从集合 中挑选出距离最小的点，这里会挑选出顶点D，集合 和 变更为： ， ，根据最新的 ，重新计算 中顶点到源点A的最短距离。
Step 5： 从集合 中挑选出距离最小的点，这里会挑选出顶点B，集合 和 变更为： ， ，根据最新的 ，重新计算 中顶点到源点A的最短距离。
Step 6： 从集合 中挑选出距离最小的点，这里会挑选出顶点G，集合 和 变更为： ， ，由于集合 为空，算法停止迭代，输出结果。
以上就是对Dijkstra算法的计算过程的简单描述。
这两个词的区别我懂，direct表示没有需要通过其他人或事物来完成的步骤。directly强调直接地执行某个动作或完成某个任务，而不需要其他步骤。给大家简单总结了两个词的含义、发音以及用法，先大概的了解一下~~
接下来让我们看下direct 和directly的其他区别：
1. 方向和路径的区别：
- direct：指在特定方向上的直线路径或最短路径。
- directly：强调没有经过中间环节或转折，直接到达目的地。
例句：
- Go straight ahead and take the first direct turn to the right. (直走，然后在第一个直接的拐角处右转。)
- The bus will take you directly to the airport without any stops. (公交车会直接把你送到机场，不停留。)
2. 效果和方式的区别：
- direct：表示直接的效果或结果，没有经过中间步骤。
- directly：表示通过直接的方式或手段来达到某个结果。
例句：
- The decision had a direct impact on the company's profits. (这个决定直接影响到公司的利润。)
- He addressed the issue directly, without any delays. (他直接处理这个问题，没有拖延。)
3. 直接和间接的区别：
- direct：强调直接的联系、关系或沟通。
- directly：表示没有任何中间人或媒介，直接与某人或某物发生联系或沟通。
例句：
- Please give me your feedback directly, without involving any third parties. (请直接给我反馈，不要涉及任何第三方。)
- She talked to him directly about the issue. (她直接和他谈了这个问题。)
4. 不需要其他步骤的区别：
- direct：表示没有需要通过其他人或事物来完成的步骤。
- directly：强调直接地执行某个动作或完成某个任务，而不需要其他步骤。
例句：
- She had direct access to the files and could make changes as needed. (她直接访问文件，根据需要进行修改。)
- I will talk to the manager directly and get this issue resolved. (我会直接和经理交谈，解决这个问题。)
5. 一对一和面对面的区别：
- direct：表示与某人直接交流或面对面交谈。
- directly：强调与某人直接进行一对一的对话或沟通。
例句：
- I will direct my questions to the speaker during the Q&A session. (在问答环节，我会向演讲者提问。)
- She addressed her concerns directly to the manager. (她直接向经理提出了她的担忧。)
最短路径法与节约法的区别：含义不同，计算不同。
一、含义不同：在这里启发式指的是一个在一个搜寻树的节点上定义的函数h(n)，用于评估从此节点到目标节点最便宜的路径。启发式通常用于资讯充分的搜寻算法，例如最好优先贪婪算法与a*。
路径指的是实现查找的方法或算法，而树是把算法变化成可见的结构图。可以理解成树是文章的结构，路径是完成一篇作文的语句。
二、计算不同：最好优先贪婪算法会为启发式函数选择最低代价的节点；a*则会为g(n)+h(n)选择最低代价的节点，此g(n)是从起始节点到目前节点的路径的确实代价。
最短路径是一个路径，最小树是一个树（支撑树），虽然二者都是要求覆盖每一个节点，但是路径和树究竟不同，后者分叉前者不分叉。
SPFA算法
可以用于存在负数边权的图，这与dijkstra算法是不同的。与Dijkstra算法与Bellman-ford算法都不同，SPFA的算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别。
在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为O(E)。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)次，此时算法退化为Bellman-ford算法，其时间复杂度为O(VE)。
