-- 图论写到这,基本概念也就告一段落了,之后还会贴一些我在工作中设计的图
-- 图论一 http://blackproof.iteye.com/blog/1727050
-- 图论二 http://blackproof.iteye.com/blog/1731542
-- 图论二 http://blackproof.iteye.com/blog/1731557
-- 图论三 http://blackproof.iteye.com/blog/1732941
-- 感谢网上资料,感谢java数据结构和算法这本书。
求带权图的最短路径,经典算法是dijkstra算法
算法不仅可以求一个顶点到令一个顶点的最短路径,而且可以列出到所有节点的最短路径
算法思路
算法用一个数据存储当前所知道的最短路径spath[],
还用一个数据去存储已经遍历的节点V
遍历所有节点,将遍历的节点放入V,将起点到其他节点的权值放入spath[]中,并重复些列操作:
1.遍历的当前节点为currentVertex,取得spath[]中最小边,并将此边的终点作为当前节点
2.遍历当前节点到其他边的距离,并且用起点->当前顶点->其他没在V的顶点的值 和 spath[]中到对应终点的边做比较,当前者小,替代后者到spath中
当完成遍历后,spath中放置的就是从顶点到各个顶点的最短路径
代码如下:
Graph:
package com.Construction.DiscrectGraph.Dijkstra; public class Graph { private final int MAX_VERTS = 20; private final int INFINITY = 1000000; private Vertex vertexList[]; private int adjMat[][]; private int nVerts; private int nTree; private DistPar sPath[]; private int currentVert; private int startToCurrent; public Graph(){ vertexList = new Vertex[MAX_VERTS]; adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; nTree = 0; for (int i = 0; i < MAX_VERTS; i++) { for (int j = 0; j < MAX_VERTS; j++) { adjMat[i][j] = INFINITY; } } sPath = new DistPar[MAX_VERTS]; } public void addVertex(char lab){ vertexList[nVerts++] = new Vertex(lab); } public void addEdge(int start,int end,int weight){ adjMat[start][end] = weight; } public void path(){ int startTree = 0; vertexList[startTree].isInTree = true; nTree = 1; for (int i = 0; i < nVerts; i++) { int tempDist = adjMat[startTree][i]; sPath[i] = new DistPar(startTree, tempDist); } while(nTree < nVerts){ int indexMin = getMin(); int minDist = sPath[indexMin].distance; if(minDist == INFINITY){ System.out.println("There are unreachable vertices"); break; } else{ currentVert = indexMin; startToCurrent = sPath[indexMin].distance; } vertexList[currentVert].isInTree = true; nTree++; adjust_sPath(); } displayPaths(); nTree = 0; for (int i = 0; i < nVerts; i++) { vertexList[i].isInTree = false; } } public int getMin(){ int minDist = INFINITY; int indexMin = 0; for (int i = 0; i < nVerts; i++) { if(!vertexList[i].isInTree && sPath[i].distance < minDist){ minDist = sPath[i].distance; indexMin = i; } } return indexMin; } public void adjust_sPath(){ int column = 1; while(column < nVerts){ if(vertexList[column].isInTree){ column++; continue; } int currentToFringe = adjMat[currentVert][column]; int startToFringe = startToCurrent + currentToFringe; int sPathDist = sPath[column].distance; if(startToFringe < sPathDist){ sPath[column].parentVert = currentVert; sPath[column].distance = startToFringe; } column++; } } public void displayPaths(){ for (int i = 0; i < nVerts; i++) { System.out.println(vertexList[i].label + " = "); if(sPath[i].distance == INFINITY) System.out.println("int"); else System.out.println(sPath[i].distance); char parent = vertexList[sPath[i].parentVert].label; System.out.println("("+parent+")"); } System.out.println(); } public static void main(String[] args) { Graph theGraph = new Graph(); theGraph.addVertex('A'); theGraph.addVertex('B'); theGraph.addVertex('C'); theGraph.addVertex('D'); theGraph.addVertex('E'); theGraph.addEdge(0, 1, 50); theGraph.addEdge(0, 3, 80); theGraph.addEdge(1, 2, 60); theGraph.addEdge(1, 3, 90); theGraph.addEdge(2, 4, 40); theGraph.addEdge(3, 2, 20); theGraph.addEdge(3, 4, 70); theGraph.addEdge(4, 1, 50); System.out.println("shortest paths"); theGraph.path(); System.out.println(); } }
算法中的spath中的对象:
package com.Construction.DiscrectGraph.Dijkstra;
public class DistPar { public int distance; public int parentVert; public DistPar(int pv,int d){ distance = d; parentVert = pv; } }
节点:
package com.Construction.DiscrectGraph.Dijkstra; public class Vertex { public char label; public boolean isInTree; public Vertex(char lab){ label = lab; isInTree = false; } }
感谢:http://2728green-rock.blog.163.com/blog/static/43636790200901211848284/
相关推荐
系统主要实现了图的创建、单源点最短路径的计算功能。依照本系统可以解决实际生活中许多路径选择问题,比如交通旅游、城市规划以及电网架设等等。系统性能稳定,适应性强,界面清晰,操作简单,适合用户使用。 课程...
基于MFC的一个程序,一个简易的地大导航程序,使用的算法是图的最短路径dijkstra算法 基于MFC的一个程序,一个简易的地大导航程序,使用的算法是图的最短路径dijkstra算法 基于MFC的一个程序,一个简易的地大导航...
最短路径算法dijkstra的matlab实现
【资源说明】 1、该资源包括项目的全部源码,下载可以直接使用! 2、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大作业和毕设项目...基于MFC的一个校园导航程序(使用图的最短路径dijkstra算法).zip
很实用去看看吧比较全面很有帮助 图的最短路径问题
数据结构 c++ 最短路径Dijkstra和Floyd
最短路径算法Dijkstra源代码,测试可以正常使用
数据结构课程设计,猴子选大王,纸牌游戏...带权图的最短路径问题 1、带权图的最短路径问题 带权图的最短路径问题即求两个顶点间长度最短的路径。 其中:路径长度不是指路径上边数的总和,而是指路径上各边的权值总和
适合于单源最短路径算法,采用的是dijkstra最短路径算法。简单易懂,本题在hdu.edu.cn上通过了,网址是http://acm.hdu.edu.cn/search.php?field=problem&key=2680。由于不能同时上传两个文件,所以我放到另一个去了...
单源最短路径Dijkstra并行程序 单源最短路径Dijkstra串行程序
Dijkstra最短路径算法的Matlab实现 包括最短路径的打印子程序
【问题描述】 试设计一个算法,求图中一个源点到其他各顶点的最短路径。 【基本要求】 (1)用邻接表表示图; (2)按长度非递减次序打印输出最短路径的长度及相应路径。
详细讲述如何实现最短路径,及c#的代码实现
C++实现的最短路径Dijkstra串行算法 包括了图的构造和生成,先生成一个有向图,再进行最短路径的查找
最短路径Dijkstra算法-最短路Dijkstra算法.rar 最短路径Dijkstra算法
单源最短路径dijkstra模板,做类似的题目可以直接套用,图的存储用邻接矩阵,带有测试数据。
最短路径Dijkstra算法,vc++6.0版的,很经典的。
最短路径Dijkstra算法PPT学习教案.pptx
最短路径-Dijkstra算法 从指定起始点向任一点搜索基于一定权重的最短路径。