首页 / 算法 / 最短路径算法的命令式、函数式版本对比分析
最短路径算法的命令式、函数式版本对比分析
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了最短路径算法的命令式、函数式版本对比分析，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8152字，纯文字阅读大概需要12分钟。
内容图文
C版本（来自 最短路径算法—Dijkstra(迪杰斯特拉)算法分析与实现(C/C++)）
1
/*
**************************************
2
* About: 有向图的Dijkstra算法实现
3
* Author: Tanky Woo
4
* Blog: www.WuTianQi.com
5
**************************************
*/
6
7 #include <iostream>
8usingnamespace std;
9 10constint maxnum = 100;
11constint maxint = 999999;
12 13 14void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
15{
16bool s[maxnum]; // 判断是否已存入该点到S集合中 17for(int i=1; i<=n; ++i)
18 {
19 dist[i] = c[v][i];
20 s[i] = 0; // 初始都未用过该点 21if(dist[i] == maxint)
22 prev[i] = 0;
23else 24 prev[i] = v;
25 }
26 dist[v] = 0;
27 s[v] = 1;
28 29// 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中
30// 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度 31for(int i=2; i<=n; ++i)
32 {
33int tmp = maxint;
34int u = v;
35// 找出当前未使用的点j的dist[j]最小值 36for(int j=1; j<=n; ++j)
37if((!s[j]) && dist[j]<tmp)
38 {
39 u = j; // u保存当前邻接点中距离最小的点的号码 40 tmp = dist[j];
41 }
42 s[u] = 1; // 表示u点已存入S集合中
43 44// 更新dist 45for(int j=1; j<=n; ++j)
46if((!s[j]) && c[u][j]<maxint)
47 {
48int newdist = dist[u] + c[u][j];
49if(newdist < dist[j])
50 {
51 dist[j] = newdist;
52 prev[j] = u;
53 }
54 }
55 }
56}
57 58void searchPath(int *prev,int v, int u)
59{
60int que[maxnum];
61int tot = 1;
62 que[tot] = u;
63 tot++;
64int tmp = prev[u];
65while(tmp != v)
66 {
67 que[tot] = tmp;
68 tot++;
69 tmp = prev[tmp];
70 }
71 que[tot] = v;
72for(int i=tot; i>=1; --i)
73if(i != 1)
74 cout << que[i] << " -> ";
75else 76 cout << que[i] << endl;
77}
78 79int main()
80{
81 freopen("input.txt", "r", stdin);
82// 各数组都从下标1开始 83int dist[maxnum]; // 表示当前点到源点的最短路径长度 84int prev[maxnum]; // 记录当前点的前一个结点 85int c[maxnum][maxnum]; // 记录图的两点间路径长度 86int n, line; // 图的结点数和路径数
87 88// 输入结点数 89 cin >> n;
90// 输入路径数 91 cin >> line;
92int p, q, len; // 输入p, q两点及其路径长度
93 94// 初始化c[][]为maxint 95for(int i=1; i<=n; ++i)
96for(int j=1; j<=n; ++j)
97 c[i][j] = maxint;
98 99for(int i=1; i<=line; ++i)
100 {
101 cin >> p >> q >> len;
102if(len < c[p][q]) // 有重边103 {
104 c[p][q] = len; // p指向q105 c[q][p] = len; // q指向p，这样表示无向图106 }
107 }
108109for(int i=1; i<=n; ++i)
110 dist[i] = maxint;
111for(int i=1; i<=n; ++i)
112 {
113for(int j=1; j<=n; ++j)
114 printf("%8d", c[i][j]);
115 printf("\n");
116 }
117118 Dijkstra(n, 1, dist, prev, c);
119120// 最短路径长度121 cout << "源点到最后一个顶点的最短路径长度: " << dist[n] << endl;
122123// 路径124 cout << "源点到最后一个顶点的路径为: ";
125 searchPath(prev, 1, n);
126 }
Java普通版本
1
import
java.util.HashSet;
2
import
java.util.LinkedList;
3
import
java.util.Queue;
4
import
java.util.Set;
5
6
public
class
Dijkstra {
7
public
static
class
PointInfo{
8
public
int
point;
9
public
int
prev_point;
10
public
int
dist;
11
public PointInfo(int p,int pp,int d){
12 point=p;
13 prev_point=pp;
14 dist=d;
15 }
16 }
17publicstaticvoid doit_more_abstract(int[][]array){
18int n=array[0].length;
19 Set<PointInfo> knownSet=new HashSet<PointInfo>();
20 Set<PointInfo> unknownSet=new HashSet<PointInfo>();
21 PointInfo source=new PointInfo(0,-1,0);
22 knownSet.add(source);
23for(int p=1;p<n;p++){
24 unknownSet.add(new PointInfo(p,-1,Integer.MAX_VALUE));
25 }
2627 PointInfo nearest=source;
28while(!unknownSet.isEmpty()){
29//update unkown points‘ dist30for(PointInfo p:unknownSet){
31if(p.dist>nearest.dist+array[nearest.point][p.point]){
32 p.prev_point=nearest.point;
33 p.dist=nearest.dist+array[nearest.point][p.point];
34 }
35 }
36//find minimum dist point37 nearest=new PointInfo(-1,-1,Integer.MAX_VALUE);
38for(PointInfo p:unknownSet){
39if(p.dist<nearest.dist){
40 nearest=p;
41 }
42 }
43//move from unknown to known44 knownSet.add(nearest);
45 unknownSet.remove(nearest);
46 }
4748 print(knownSet);
49 }
50privatestatic PointInfo getPoint(Set<PointInfo> pset,int index){
51for(PointInfo p:pset){
52if(p.point==index){
53return p;
54 }
55 }
56returnnull;
57 }
5859privatestaticvoid print(Set<PointInfo> knownSet){
60for(int i=0;i<knownSet.size();i++){
61int index=i;
62 log("node:"+(index+1)+",weight:"+getPoint(knownSet,index).dist);
63while(index>=0){
64 log(""+(index+1));
65 index=getPoint(knownSet,index).prev_point;
66 }
67 }
68 }
69publicstaticint[][] makeUpGraph(){
70int[][]array={
71 {0, 15, 10, Infinite, Infinite, 1},
72 {15, 0, 19, 33, 1, Infinite},
73 {10, 19, 0, 27, Infinite, Infinite},
74 {Infinite, 33, 27, 0, 3, 45},
75 {Infinite, 1, Infinite, 3, 0, 1},
76 {1, Infinite, Infinite, 45, 1, 0}
7778 };
79return array;
80 }
81publicstaticvoid log(String s){
82 System.out.println(s);
83 }
84publicstaticvoid main(String[]args){
85 doit_more_abstract(makeUpGraph());
86 }
87 }
Java 函数式实现版本
1
import
java.util.HashSet;
2
import
java.util.LinkedList;
3
import
java.util.Queue;
4
import
java.util.Set;
5
public
class
Dijkstra {
6
public
static
class
PointInfo{
7
public
int
point;
8
public
int
prev_point;
9
public
int
dist;
10
public PointInfo(int p,int pp,int d){
11 point=p;
12 prev_point=pp;
13 dist=d;
14 }
15 }
16privatestatic PointInfo getPoint(Set<PointInfo> pset,int index){
17for(PointInfo p:pset){
18if(p.point==index){
19return p;
20 }
21 }
22returnnull;
23 }
2425privatestaticvoid print(Set<PointInfo> knownSet){
26for(int i=0;i<knownSet.size();i++){
27int index=i;
28 log("node:"+(index+1)+",weight:"+getPoint(knownSet,index).dist);
29while(index>=0){
30 log(""+(index+1));
31 index=getPoint(knownSet,index).prev_point;
32 }
33 }
34 }
3536publicstaticvoid doit_functional_way(int[][]array){
37int n=array[0].length;
38 Set<PointInfo> knownSet=new HashSet<PointInfo>();
39 Set<PointInfo> unknownSet=new HashSet<PointInfo>();
40 PointInfo source=new PointInfo(0,-1,0);
41 knownSet.add(source);
42for(int p=1;p<n;p++){
43 unknownSet.add(new PointInfo(p,-1,Integer.MAX_VALUE));
44 }
45 PointInfo nearest=source;
46 Set<PointInfo> finalSet=iterate(knownSet, unknownSet, nearest, array);
47 print(finalSet);
48 }
4950privatestatic Set<PointInfo> iterate(Set<PointInfo> knownSet,Set<PointInfo> unknownSet,PointInfo nearest,int[][]array){
51if(unknownSet.isEmpty()){
52return knownSet;
53 }
54//update unkown points‘ dist55for(PointInfo p:unknownSet){
56if(p.dist>nearest.dist+array[nearest.point][p.point]){
57 p.prev_point=nearest.point;
58 p.dist=nearest.dist+array[nearest.point][p.point];
59 }
60 }
61//find minimum dist point62 nearest=new PointInfo(-1,-1,Integer.MAX_VALUE);
63for(PointInfo p:unknownSet){
64if(p.dist<nearest.dist){
65 nearest=p;
66 }
67 }
68//move from unknown to known69 knownSet.add(nearest);
70 unknownSet.remove(nearest);
7172return iterate(knownSet, unknownSet, nearest, array);
73 }
7475publicstaticint[][] makeUpGraph(){
76int[][]array={
77 {0, 15, 10, Infinite, Infinite, 1},
78 {15, 0, 19, 33, 1, Infinite},
79 {10, 19, 0, 27, Infinite, Infinite},
80 {Infinite, 33, 27, 0, 3, 45},
81 {Infinite, 1, Infinite, 3, 0, 1},
82 {1, Infinite, Infinite, 45, 1, 0}
8384 };
85return array;
86 }
87publicstaticvoid main(String[]args){
88 doit_functional_way(makeUpGraph());
89 }
90 }
如果你认真分析最短路径算法，会发现它实际包含了三个核心的概念：
已知最短路径的点集合A（每个点的信息包括：点的名字、路径上前一个点的名字、路径长度）
未知最短路径的点集合B（每个点的信息包括：点的名字、路径上前一个点的名字prev_point、路径长度distance）
刚刚从集合B中选出的距离最小的点nearest_point。
执行过程
初始状态：
集合A：仅包含源点
集合B：包含除源点外的所有点
nearest_point：源点
迭代的过程是
根据nearest_point，更新集合B中每个点的prev_point、distance
从集合B中选出distance最小的点，作为新的nearest_point
将nearest_point从集合B移动到集合A中
结束条件：当集合B为空时，算法结束
个人认为，除了代码运行速度，比较C、Java、Java函数式三个版本implementation的最重要标准是：是否能够直接有力的体现出以上三个核心概念（集合A、集合B、nearest_point）和执行过程。大家如果有耐心读完三个版本的代码，会发现Java两个在这一点上明显比C版本提上了一个层次。
Java普通版本和Java函数式版本的差别在于While循环和iterate递归函数，iterate递归函数更加直观了表现出了“状态变换”。实际上，整个迭代过程就是前一个状态(集合A，集合B，nearest_point)=>后一个状态（集合A、集合B、nearest_point）的变换。
很多函数式语言的拥护者都说：函数式语言的优点是无副作用。我觉得这完全是人与亦云的胡扯。恰恰相反，在使用函数式语言写代码时，它带给我最大的障碍就是无法使用副作用。目前在我眼中，它的最美之处是function as first class object。其次则是对抽象概念和状态变换过程的优雅表达方式。
（我本来用Haskell作为函数式版本的代码示例，但考虑到很多同学大概对这种语言不熟悉，于是使用Java，大家可以看到，即使在imperative语言的环境中，依然可以运用函数式语言的思维方式写出优雅的代码。）
原文：http://www.cnblogs.com/linghuaichong/p/3810932.html
内容总结
以上是互联网集市为您收集整理的最短路径算法的命令式、函数式版本对比分析全部内容，希望文章能够帮你解决最短路径算法的命令式、函数式版本对比分析所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】