❶ matlab实现floyd算法 已知距离矩阵和权值矩阵 求最短路径
希望可以帮到你。
function [D,path]=floyd(a)
n=size(a,1);
D=a;
path=zeros(n,n);
for i=1:n
for j=1:n
if D(i,j)~=inf
path(i,j)=j;
end
end
end
for k=1:n
for i=1:n
for j=1:n
if D(i,k)+D(k,j)<D(i,j)
D(i,j)=D(i,k)+D(k,j);
path(i,j)=path(i,k)
end
end
end
end
function [L,R]=router(D,path,s,t)
L=zeros(0,0);
R=s;
while 1
if s==t
L=fliplr(L);
L=[0,L];
return
end
L=[L,D(s,t)];
R=[R,path(s,t)];
s=path(s,t);
end
❷ 求Matlab Floyd算法代码，要求能计算矩阵任意两节点的最短距离，得到所有可能的路径
去codesoso和pudn看看吧，哪里应该有你想要的东西。。。
❸ 图无负环，最短路径算法（Floyd-Warshall，Bellman-Ford算法，MATLAB实现）输出环路，是什么原因
§1 Dijkstra算法
Dijkstra算法思想
Dijkstra算法思想为：设G=(V,E)是一个带权有向图（无向可以转化为双向有向），把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
Dijkstra算法具体步骤
（1）初始时，S只包含源点，即S＝{v}，v的距离dist[v]为0。U包含除v外的其他顶点，U中顶点u距离dis[u]为边上的权值（若v与u有边） ）或∞（若u不是v的出边邻接点即没有边<v,u>）。
（2）从U中选取一个距离v(dist[k])最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u∈ U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权(即如果dist[k]+w[k,u]<dist[u]，那么把dist[u]更新成更短的距离dist[k]+w[k,u])。
（4）重复步骤（2）和（3）直到所有顶点都包含在S中(要循环n-1次)。
╝①
Dijkstra算法实现
╔
直接实现
最简单的实现方法就是，在每次循环中，再用一个循环找距离最短的点，然后用任意的方法更新与其相邻的边，时间复杂度显然为O(n²)
对于空间复杂度：如果只要求出距离，只要n的附加空间保存距离就可以了（距离小于当前距离的是已访问的节点，对于距离相等的情况可以比较编号或是特殊处理一下）。如果要求出路径则需要另外V的空间保存前一个节点，总共需要2n的空间。
╝②
╔
Cpp代码
/*********************************
* 最短路径---Dijkstra算法实现
* HDU：2544
* BLOG:www.cnblogs.com/newwy
* AUTHOR:Wang Yong
**********************************/
#include <iostream>
#define MAX 100
#define INF 1000000000
using namespace std;
int dijkstra (int mat[][MAX],int n, int s,int f)
{
int dis[MAX];
int mark[MAX];//记录被选中的结点
int i,j,k = 0;
for(i = 0 ; i < n ; i++)//初始化所有结点，每个结点都没有被选中
mark[i] = 0;
for(i = 0 ; i < n ; i++)//将每个结点到start结点weight记录为当前distance
{
dis[i] = mat[s][i];
//path[i] = s;
}
mark[s] = 1;//start结点被选中
//path[s] = 0;
dis[s] = 0;//将start结点的的距离设置为0
int min ;//设置最短的距离。
for(i = 1 ; i < n; i++)
{
min = INF;
for(j = 0 ; j < n;j++)
{
if(mark[j] == 0 && dis[j] < min)//未被选中的结点中，距离最短的被选中
{
min = dis[j] ;
k = j;
}
}
mark[k] = 1;//标记为被选中
for(j = 0 ; j < n ; j++)
{
if( mark[j] == 0 && (dis[j] > (dis[k] + mat[k][j])))//修改剩余结点的最短距离
{
dis[j] = dis[k] + mat[k][j];
}
}
}
return dis[f];
}
int mat[MAX][MAX];
int main()
{
int n,m;
while(scanf("%d %d",&n,&m))
{
int a,b,dis;
if(n == 0 || m == 0)
break;
int i,j;
for(i = 0 ; i < n;i++)
for(j = 0 ; j < n; j++)
mat[i][j] = INF;
for(i = 0 ; i < m ;i++)
{
scanf("%d %d %d",&a,&b,&dis);
--a,--b;
if(dis < mat[a][b] || dis < mat[b][a])
mat[a][b] = mat[b][a] = dis;
}
int ans = dijkstra(mat,n,0,n-1);
printf("%d\n",ans);
}
}
╝⑤
╔
二叉堆实现
使用二叉堆(Binary Heap)来保存没有扩展过的点的距离并维护其最小值，并在访问每条边的时候更新，可以把时间复杂度变成O((V+E)logV)。
当边数远小于点数的平方时，这种算法相对来说有很好的效果。但是当E=O(V2)时（有时候表现为不限制边的条数），用二叉堆的优化反倒会更慢。因为此时的复杂度是O(V+V*2logV)，小于不用堆的实现的O(n²)的复杂度。
另外此时要用邻接表保存边，使得扩展边的总复杂度为O(E)，否则复杂度不会减小。
空间复杂度：这种算法需要一个二叉堆，及其反向指针，另外还要保存距离，所以所用空间为3V。如果保存路径则为4V。
具体思路：先将所有的点插入堆，并将值赋为极大值(maxint/maxlongint)，将原点赋值为0，通过松弛技术（relax）进行更新以及设定为扩展。
╝②
╔
C代码
int GraphDijk(struct Graph *g, int root, int *parent, int *distance)
{
// 将除根结点之外的点都放入堆中，设置所有键为INFINITY
// 遍历根结点发出的边，将其最短路径设为相应权值，并维持堆性质
// RemoveTop，此结点已经取最短路径，如果为INFINITY，则终止算法
// 否则，将其状态设为已标记，并设为根结点
// loop back
parent[root] = root;
int reflection[g->V];
int heap_real[g->V - 1];
for (int i=0,j=0; i < g->V; i++) {
if (i == root) {
distance[i] = 0;
} else {
distance[i] = INFINITY;
heap_real[j++] = i;
reflection[i] = j;
}
}
struct Edge *e;
struct list_t *iter;
int *heap = heap_real - 1;
int base = 0; /* euqal to distance[root] */
int size = g->V - 1;
int length;
do {
iter = list_next(&(g->vertices + root)->link);
for (; iter; iter = list_next(iter)) {
e = list_entry(iter, struct Edge, link);
length = base + e->weight;
if (length < distance[e->to]) {
HeapDecreaseKey(heap, size,
distance, reflection,
reflection[e->to], length);
parent[e->to] = root;
}
}
root = HeapRemoveTop(heap, size, distance, reflection);
base = distance[root];
if (distance[root] == INFINITY) {
/* remain nodes in heap is not accessible */
return g->V - (size + 1); /* 返回强连通分支结点数 */
}
} while (size);
/* successfull end algorightm */
return g->V;
}
╝④
再献上一个实现
╔
C代码
/*很裸很水的最短路，练习二叉堆优化的Dijstra～
之前二叉堆优化的Prim敲了好几遍前后花了不下八个小时调试还是没有调试成功，
但是还好，熟悉了优先队列的操作。
十几天后的今天重新想起这个，终于调出来了堆优化的Dijstra。理解之后还是蛮简单的。
一些写法并不是最优的，例如heap的实现中可以减少交换元素等。但是有这个自己写的AC
过的Dijkstra在，以后写二叉堆优化的Prim/Dijkstra和其它优先队列的题目就可以拿它对照着Debug了。
2011-07-24 23:00
*/
#include <stdio.h>
#define MAXN 1200
#define MAXM 1200000
#define INF 19930317
struct node
{
int d, v, p;
}heap[MAXN];
int pos[MAXN], hl;
int e[MAXM], cost[MAXM], next[MAXM], g[MAXN], size;
int m, n, s, t;
void insert(int u, int v, int w)
{
e[++size] = v;
next[size] = g[u];
cost[size] = w;
g[u] = size;
}
void swap(int a, int b)
{
heap[0] = heap[a];
heap[a] = heap[b];
heap[b] = heap[0];
pos[heap[a].v] = a;
pos[heap[b].v] = b;
}
void heapfy()
{
int i = 2;
while (i <= hl)
{
if ((i < hl) && (heap[i + 1].d < heap[i].d))
i++;
if (heap[i].d < heap[i >> 1].d)
{
swap(i, i >> 1);
i <<= 1;
}
else
break;
}
}
void decrease(int i)
{
while ((i != 1) && (heap[i].d < heap[i >> 1].d))
{
swap(i, i >> 1);
i >>= 1;
}
}
void relax(int u ,int v, int w)
{
if (w + heap[pos[u]].d < heap[pos[v]].d)
{
heap[pos[v]].p = u;
heap[pos[v]].d = w + heap[pos[u]].d;
decrease(pos[v]);
}
}
void delete_min()
{
swap(1, hl);
hl--;
heapfy();
}
void init()
{
int u ,v ,w, i;
scanf("%d%d", &m, &n);
for (i = 1; i <= m; i++)
{
scanf("%d%d%d", &u, &v, &w);
insert(u, v, w);
insert(v, u, w);
}
s = 1;
t = n;
}
int dijkstra()
{
int u, p, i;
for (i = 1; i <= n; i++)
{
heap[i].v = pos[i] = i;
heap[i].d = INF;
}
heap[s].p = s;
heap[s].d = 0;
swap(1, s);
hl = n;
while (hl)
{
u = heap[1].v;
delete_min();
p = g[u];
while (p)
{
if (pos[e[p]] <= hl)
relax(u, e[p], cost[p]);
p = next[p];
}
}
}
int main()
{
init();
dijkstra();
printf("%d\n", heap[pos[t]].d);
return 0;
}
╝③
╔
菲波那契堆实现
用类似的方法，使用Fibonacci Heap可以将复杂度降到O(E+VlogV)，但实现比较麻烦。因此这里暂不列举。
❹ floyd算法matlab
a矩阵是邻接矩阵，对角线上为o，其余位置数字表示的是两点之间距离，比如a(1,2)=2,表示从第一个点到第二个点的距离为2.inf是无穷大的意思，这里表示没有直接沟通这两点的路。
n=length(d);设定n为d矩阵的长度。
接下来的两重循环，得到的r矩阵是n*n的矩阵，它每个数据表示的是路径，比如：r(1,3)=1;表示路径为：1-1-3.这里是初始化路径了。
后面的三重循环是floyd算法的关键所在，就是更新路线了。里面的那个判断指的是：
假设有3个点，1
2
3；如果我从1-2-3之间总距离小于1-3的距离，那么我r(1,3)=2；这就是选取更近的路线了。
最后的两个判断是为了不让曾经走过的点再次被遍历。就是不回头的意思了，这个一般都可以忽略了，你照打上去就是了。
不知道这样的解释你是否满意。
❺ 求matlab大神告诉我floyd算法的matlab实现，，，以及我目前出现的各种报错原因
存在负权的图中没有最短路的概念。负权回路本来就没有最短路。因为可以绕着负环一直转下去。有两个顶点:,->-->-然后我再由->那就成了-。
❻ 求程序 在matlab上用Dijkstra和Floyd算法求出v1到v8的最短路径。。
function[distance,path]=Dijkstra(W,st,e)
n=length(W);
D=W(st,:);
visit=ones(1:n);
visit(st)=0;
parent=zeros(1,n);
path=[];
fori=1:n-1
temp=[];
forj=1:n
ifvisit(j)
temp=[tempD(j)];
else
temp=[tempinf];
end
end
[~,index]=min(temp);
visit(index)=0;
fork=1:n
ifD(k)>D(index)+W(index,k)
D(k)=D(index)+W(index,k);
parent(k)=index;
end
end
end
distance=D(e);
t=e;
whilet~=st&&t>0
path=[t,path];
p=parent(t);t=p;
end
path=[st,path];%最短路径
end
W=[0310InfInfInfInfInf;
30Inf5InfInfInfInf;
10Inf06InfInfInfInf;
Inf5604InfInfInf;
InfInfInf4095Inf;
InfInfInfInf9034;
InfInfInf105306;
InfInfInfInfInf460];
[distance,path]=Dijkstra(W,1,8);
>>distance
distance=
23
>>path
path=
124578
❼ 求matlab高手，帮我解决一下floyd算法！！急急急
//假期在家做的，网上这类算法很多，思想都差不多
#include<iostream>
using namespace std;
int N; //顶点个数
int max = 10000; //max代表两点之间没有路径存在
float ** inPut(){
int edge,m,n,w,i;
cout<<"请输入顶点数：";
cin>>N;
N = N+1; //矩阵（数组）下标从1开始计数，方便操作
float **C = new float*[N]; //矩阵C为图的初始邻接矩阵
for(i = 1; i<N; i++)
*(C+i) = new float[N];
for( i = 1; i<N; i++) //邻接矩阵初始化
for(int j = 1; j<N; j++){
if(i == j)
C[i][j] = 0; //矩阵对角线上的值初始为0，其他为max
else C[i][j] = max;
}
cout<<"请输入边数：";
cin>>edge;
cout<<"请输入边及权值："<<endl;
for(i = 0; i<edge; i++){
cin >> m >> n >> w;
C[m][n] = w;
}
return C;
}
void Floyd(float **C){
int i,j;
float **A = new float*[N]; //矩阵A最终存放修改后的路径长度
int **path = new int*[N]; //矩阵path记录两点之间的路径
for(i = 1; i<N; i++)
*(A+i) = new float[N];
for(i = 1; i<N; i++)
*(path+i) = new int[N];
for(i = 1; i<N; i++) //设置矩阵A和path的初值
for(j = 1; j<N; j++){
if(C[i][j] != max)
path[i][j] = j; //存在路径，记录下终点下标值
else path[i][j] = -1; //不存在路径用-1表示
A[i][j] = C[i][j];
}
//修改路径长度（矩阵A）和路径（矩阵path）
for(int k = 1; k<N; k++) //试图将顶点k扩充到最短路径path矩阵中
for(i = 1; i <N; i++)
for(j = 1; j<N; j++)
if( A[i][j] > ( A[i][k]+A[k][j] ) ){//判断顶点i到j的权值是否大于从i经k到j的权值，取二者较小者记录下来
A[i][j] = ( A[i][k]+A[k][j]);
path[i][j] = path[i][k]; //记录下中间顶点k值
}
cout << endl << endl;
cout << "初始邻接矩阵C[N][N]" << endl;
for( i = 1; i<N; i++){
for(j = 1; j<N; j++){
cout << C[i][j] << "\t";
}
cout << endl;
}
cout << endl << endl;
cout << "修改后的路径长度矩阵" << endl;
for( i = 1; i<N; i++){
for(j = 1; j<N; j++){
cout << A[i][j] << "\t";
}
cout << endl;
}
cout << endl;
cout << endl;
cout<<"路径矩阵"<<endl;
for( i = 1; i<N; i++){
for(j = 1; j<N; j++){
cout << path[i][j] << "\t";
}
cout << endl;
}
cout << endl << endl;
cout << "所有顶点对之间的最短路径的权值及其路径" << endl;
for(i = 1; i<N; i++){
cout << endl;
for(j = 1; j<N; j++){
cout << A[i][j] << "\t"; //输出i-->j的权值
int next = path[i][j]; //顶点i到j的路径，i后的第一个后继顶点
if(next == -1) //路径不存在
cout << i << " 到 " << j << " 没有路径" << endl;
else {
cout<<i; //起点
while(next != j){ //i、j之间存在中间顶点
cout << "-->" << next;
next = path[next][j]; //寻找下一个中间顶点
}
cout << "-->" << j << endl; //终点
}
}
}
}
int main(int argc, char* argv[]){
float **C;
C = inPut(); //邻接矩阵的初始化
Floyd(C);
return 0;
}
/*
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
*/
❽ 想用Matlab中floyd算法求最短路径，可是不太会使用MATLAB2014怎么办怎么导入Excel表进去
可以用下列命令，将Excel导入数组A中
A=xlsread('1.xls');
x=A(:,1); Excel第一列数值储存到x列矩阵
y=A(:,2); Excel第二列数值储存到x列矩阵
z=A(:,3); Excel第三列数值储存到x列矩阵
。。。。。。
用xlswrite('2..xls', M)，将数组M写入2..xls中
❾ floyd算法求最短路径
Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。
优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单
缺点：时间复杂度比较高，不适合计算大量数据。
时间复杂度:O(n^3)；空间复杂度:O(n^2)；
任意节点i到j的最短路径两种可能：
直接从i到j；
从i经过若干个节点k到j。
map（i，j）表示节点i到j最短路径的距离，对于每一个节点k，检查map（i，k）+map（k，j）小于map(i，j),如果成立，map（i，j） = map（i，k）+map（k，j）；遍历每个k，每次更新的是除第k行和第k列的数。
步骤：
第1步：初始化map矩阵。
矩阵中map[i][j]的距离为顶点i到顶点j的权值；
如果i和j不相邻，则map[i][j]=∞。
如果i==j，则map[i][j]=0;
第2步：以顶点A(假设是第1个顶点)为中介点，若a[i][j] > a[i][1]+a[1][j]，则设置a[i][j]=a[i][1]+a[1][j]。
❿ 十万火急需要用floyd算法求最短路径~~~需要程序~~~十万火急~~~~~
A*算法是启发式搜索，适合点对点的最短路径，单源单汇的情况
Floyd是动态规划的一种，可以求出任意两点之间的最短路径
Dijkstra是贪婪算法的一种，求一点到其他所有点的最短路，即所谓的单源最短路算法
从时间复杂度来说
Floyd是O(N^3)
Dijkstra是O(N^2)
而启发式搜索就不好说了……
结果当然是一样的，都是最短路，但是适用情形和时空开销就不同了
2011年