图论matlab代码整理

以下是一些常用的图论算法的 Matlab 代码：

1. Dijkstra算法求最短路：

function [dist,prev]=dijkstra(G,source)

n=length(G);
dist=inf(1,n);
dist(source)=0;
S=1:n;
prev=zeros(1,n);

while not(isempty(S))
    [~,u]=min(dist(S));
    S(S==u)=[];
    for v=S
        if G(u,v)
            alt=dist(u)+G(u,v);
            if alt<dist(v)
                dist(v)=alt;
                prev(v)=u;
            end
        end
    end
end

2. Bellman-Ford算法求最短路：

function [dist,prev]=bellman_ford(G,source)

n=length(G);
dist=inf(1,n);
dist(source)=0;
prev=zeros(1,n);

for i=1:n-1
    for u=1:n
        for v=1:n
            if G(u,v)
                alt=dist(u)+G(u,v);
                if alt<dist(v)
                    dist(v)=alt;
                    prev(v)=u;
                end
            end
        end
    end
end

for u=1:n
    for v=1:n
        if G(u,v)
            if dist(u)+G(u,v)<dist(v)
                error('Negative cycle detected');
            end
        end
    end
end

3. Floyd算法求最短路：

function [D,next]=floyd(G)

n=length(G);
D=G;
next=zeros(size(G));

for k=1:n
    for i=1:n
        for j=1:n
            if D(i,j)>D(i,k)+D(k,j)
                D(i,j)=D(i,k)+D(k,j);
                next(i,j)=k;
            end
        end
    end
end

4. Prim算法求最小生成树：

function [T,total_cost]=prim(G)

n=length(G);
total_cost=0;
T=zeros(n);
D=inf(1,n);
visited=false(1,n);
D(1)=0;

for i=1:n-1
    [~,u]=min(D);
    visited(u)=true;
    for v=1:n
        if G(u,v)~=0 && ~visited(v) && G(u,v)<D(v)
            D(v)=G(u,v);
            T(u,v)=G(u,v);
            T(v,u)=G(u,v);
        end
    end
    total_cost=total_cost+D(u);
    D(u)=inf;
end

5. Kruskal算法求最小生成树：

function [T,total_cost]=kruskal(G)

n=length(G);
[G_sorted,I]=sort(G(:));
T=zeros(n);
total_cost=0;

for k=1:length(G_sorted)
    [i,j]=ind2sub([n,n],I(k));
    if G(i,j)~=0 && ~connected(T,i,j)
        T(i,j)=G(i,j);
        T(j,i)=G(i,j);
        total_cost=total_cost+G(i,j);
    end
end
end

function c=connected(T,i,j)
n=size(T,1);
S=zeros(1,n);
S(i)=1;
while true
    old_S=S;
    S=max(S,T*S);
    if isequal(S,old_S)
        break
    end
end
c=S(j);
end

这些代码可以作为图论算法学习和实践的参考。