图论matlab代码整理
时间: 2023-07-09 13:28:29 浏览: 43
以下是一个简单的图论算法的 Matlab 代码整理,包括最短路径算法和最小生成树算法。
最短路径算法:
Dijkstra算法:
```matlab
function [dist,pred] = dijkstra(A,s)
% Dijkstra's single-source shortest-path algorithm.
% ADJACENCY MATRIX A: A(i,j) = 0 if (i,j) is not an edge, otherwise
% A(i,j) = w(i,j) is the weight of the edge.
% SOURCE VERTEX s
% DIST vector of shortest distances from s to each vertex
% PRED vector of predecessors along shortest path from s
% to each vertex
n = length(A);
dist = inf(1,n);
pred = ones(1,n)*NaN;
visited = zeros(1,n);
dist(s) = 0;
for i=1:n-1
[mindist, u] = min(dist.*(~visited));
visited(u) = 1;
for v=1:n
if ~visited(v) && A(u,v)~=0
if dist(u) + A(u,v) < dist(v)
dist(v) = dist(u) + A(u,v);
pred(v) = u;
end
end
end
end
```
Bellman-Ford算法:
```matlab
function [dist,pred] = bellman_ford(A,s)
% Bellman-Ford algorithm for single-source shortest paths.
% ADJACENCY MATRIX A: A(i,j) = 0 if (i,j) is not an edge, otherwise
% A(i,j) = w(i,j) is the weight of the edge.
% SOURCE VERTEX s
% DIST vector of shortest distances from s to each vertex
% PRED vector of predecessors along shortest path from s
% to each vertex
% Returns true if there are no negative cycles in the graph, and
% false otherwise.
n = length(A);
dist = inf(1,n);
pred = ones(1,n)*NaN;
dist(s) = 0;
for i=1:n-1
for u=1:n
for v=1:n
if A(u,v)~=0
if dist(u) + A(u,v) < dist(v)
dist(v) = dist(u) + A(u,v);
pred(v) = u;
end
end
end
end
end
for u=1:n
for v=1:n
if A(u,v)~=0
if dist(u) + A(u,v) < dist(v)
negative_cycle = true;
return
end
end
end
end
negative_cycle = false;
```
最小生成树算法:
Prim算法:
```matlab
function [T,total] = prim(A,r)
% Prim's minimum spanning tree algorithm.
% ADJACENCY MATRIX A: A(i,j) = 0 if (i,j) is not an edge, otherwise
% A(i,j) = w(i,j) is the weight of the edge.
% ROOT NODE r
% T sparse matrix representing the minimum spanning tree.
% Total weight of the tree.
n = length(A);
T = sparse(n,n);
key = inf(1,n);
pred = zeros(1,n);
visited = zeros(1,n);
key(r) = 0;
for i=1:n
[u, mindist] = min(key.*(~visited));
visited(u) = 1;
if u~=r
T(pred(u),u) = mindist;
T(u,pred(u)) = mindist;
end
total = total + mindist;
for v=1:n
if A(u,v)~=0 && ~visited(v) && A(u,v) < key(v)
key(v) = A(u,v);
pred(v) = u;
end
end
end
```
Kruskal算法:
```matlab
function [T,total] = kruskal(A)
% Kruskal's minimum spanning tree algorithm.
% ADJACENCY MATRIX A: A(i,j) = 0 if (i,j) is not an edge, otherwise
% A(i,j) = w(i,j) is the weight of the edge.
% T sparse matrix representing the minimum spanning tree.
% Total weight of the tree.
n = length(A);
T = sparse(n,n);
total = 0;
[EI,EJ,EV] = find(triu(A));
[EV,ind] = sort(EV);
EI = EI(ind);
EJ = EJ(ind);
for k=1:length(EI)
i = EI(k);
j = EJ(k);
if length(nonzeros(T(:,i))) < n-1 || length(nonzeros(T(:,j))) < n-1
T(i,j) = EV(k);
T(j,i) = EV(k);
total = total + EV(k);
elseif cycles(T,i,j)
continue
else
T(i,j) = EV(k);
T(j,i) = EV(k);
total = total + EV(k);
end
end
```
这些算法都是经典的图论算法,它们可以帮助你解决许多实际问题。