see
http://eriol.iteye.com/blog/1186408
http://blog.csdn.net/vinglemar/article/details/3605813
import java.util.ArrayList;
import java.util.List;
public class FloydInGraph {
/**
* 图 邻接矩阵 最短路径 弗洛伊德算法
*/
private static int INF=Integer.MAX_VALUE;
//dist[i][j]=INF<==>no edges between i and j
private int[][] dist;
//the distance between i and j.At first,dist[i][j] is the weight of edge [i,j]
private int[][] path;
private List<Integer> result=new ArrayList<Integer>();
public static void main(String[] args) {
FloydInGraph graph=new FloydInGraph(5);
int[][] matrix={
{INF,30,INF,10,50},
{INF,INF,60,INF,INF},
{INF,INF,INF,INF,INF},
{INF,INF,INF,INF,30},
{50,INF,40,INF,INF},
};
int begin=0;
int end=4;
graph.findCheapestPath(begin,end,matrix);
List<Integer> list=graph.result;
System.out.println(begin+" to "+end+",the cheapest path is:");
System.out.println(list.toString());
System.out.println(graph.dist[begin][end]);
}
public void findCheapestPath(int begin,int end,int[][] matrix){
floyd(matrix);
result.add(begin);
findPath(begin,end);
result.add(end);
}
public void findPath(int i,int j){
int k=path[i][j];
if(k==-1)return;
findPath(i,k);
result.add(k);
findPath(k,j);
}
public void floyd(int[][] matrix){
int size=matrix.length;
//initialize dist and path
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
path[i][j]=-1;
dist[i][j]=matrix[i][j];
}
}
for(int k=0;k<size;k++){
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
if(dist[i][k]!=INF&&
dist[k][j]!=INF&&
dist[i][k]+dist[k][j]<dist[i][j]){//dist[i][k]+dist[k][j]>dist[i][j]-->longestPath
dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=k;
}
}
}
}
}
public FloydInGraph(int size){
this.path=new int[size][size];
this.dist=new int[size][size];
}
}
- 大小: 11.3 KB
分享到:
相关推荐
本程序因时间问题一直没有修改其通用性,这是一个最大的问题,希望有兴趣的...所以请朋友们在运行的时候,如想修改起先路径请自已的定义的时候自行修改,同时也要修改程序本身的一些相关数据,如循环长度等。。。。。
用c++ 实现图—邻接矩阵的最短路径算法 已经测试过。
C# floyd算法 求最短路径 C# floyd算法 求最短路径 C# floyd算法 求最短路径
floyd计算最短路径,只需要更改邻接矩阵
假设图中各边的权值都相等,以邻接矩阵和邻接表为存储结构,分别写出算法: (1)求顶点vi到顶点vj(i<>j)的最短路径 (2)求源点vi到其余各顶点的最短路径 要求输出路径上的所有顶点(利用BFS遍历的思想)
//图的邻接矩阵表示,求最短路径算法 #include "iostream.h" #include "stdio.h" #include "assert.h" #include "queue.h" #include "sqlist.h" //#include "minspantree.h
迪杰斯特拉最短路径算法和分析,有图有真相
Dijkstra算法 邻接矩阵 最短路径
基于邻接矩阵存储的图的最短路径问题,可以很好的学习C++和数据结构
Floyd算法 邻接矩阵 最短路径 上机作业没问题
可以用邻接表和邻接矩阵求最短路径 实现图的邻接矩阵和邻接表存储结构; 完成基于邻接矩阵或邻接表的深度优先搜索遍历及广度优先搜索遍历; 实现从键盘输入任意一对顶点,求出顶点间的最短路径。
用邻接举证实现求顶点间最短路径 MGraph G; //创建图结构 CreatTu(G); //显示图结构 Disp(G); //寻找最短路径 simpleline(G);
用图的邻接表求最短路径,用邻接表 邻接表 邻接表
NULL 博文链接:https://128kj.iteye.com/blog/1663164
构造邻接矩阵,利用Floyd算法求最短路径。课程设计~~~
设计一个旅游景点导游模拟程序,为来访的客人提供景点最短路径的信息查询服务,任意选取n城市,构成一个有向带权图,图中顶点表示城市,边上的权值表示两点间的距离,根据用户指定的始点和终点输出相应的最短路径。
用vc++6.0实现图-邻接矩阵-最短路径.数据结构课程必备,有一定参考价值。
最短路径-Dijkstra算法 从指定起始点向任一点搜索基于一定权重的最短路径。
求最短路径及其最短路径大小 matlab 图论 [P u]=f_path(W) W是邻接矩阵 P是最短路径 u是最短路径大小
求最短路径的Floyd算法实现,无向图和有向图均适用。1先区别有向图和无向图,2输入顶点数和边数并检查合法性,3输入每边的起点、终点、权重并检查合法性,并初始化邻接矩阵和路径矩阵,4调用自定义函数Floyd