bellman ford java_Java C 实现Bellman-ford算法
package com.cn.tree;
public class MyException extends Exception {
private static final long serialVersionUID = 1L;
public MyException(String str) {
super(str);
}
public MyException() {}
}
package com.cn.graph;
import com.cn.tree.MyException;
/**
* 很明顯時(shí)間復(fù)雜度為O(VE),因?yàn)槊恳淮涡枰獙?duì)邊進(jìn)行松弛，所以我們采用保存邊的方式來(lái)存儲(chǔ)圖的的信息。
* p保存的是前驅(qū)節(jié)點(diǎn)，d保存的是源點(diǎn)到每一個(gè)點(diǎn)的最短距離。我們最后又做了一次判斷，如果還有可以松弛
* 的邊，那么可以保證的是圖中有負(fù)權(quán)的環(huán)存在，這樣的話就沒(méi)有最短路徑只說(shuō)了，可以無(wú)限小。
*
* @author daijope
*
*/
public class BellmanFord {
private static final int m = 10000;
public static void main(String[] args) throws MyException {
Adge a1 = new Adge(0, 1, -1);
Adge a2 = new Adge(0, 2, 4);
Adge a3 = new Adge(1, 2, 3);
Adge a4 = new Adge(3, 1, 1);
Adge a5 = new Adge(1, 3, 2);
Adge a6 = new Adge(3, 2, 5);
Adge a7 = new Adge(1, 4, 2);
Adge a8 = new Adge(4, 3, -3);
Adge[] as = new Adge[]{a1, a2, a3, a4, a5, a6, a7, a8};
int[] d = new int[5];
int[] p = new int[5];
d[0] = 0;
p[0] = 0;
for (int i = 1; i < d.length; i++) {
d[i] = m;
p[i] = -1;
}
bellman_Ford(as, d, p);
for (int i = 0; i < d.length; i++) {
System.out.println(d[i]);
}
}
private static void bellman_Ford(Adge[] as, int[] d, int[] p) throws MyException {
for(int i = 1; i < d.length; i++) {
for (int j = 0; j < as.length; j++) {
if (d[as[j].getV()] > d[as[j].getU()] + as[j].getW()) {
d[as[j].getV()] = d[as[j].getU()] + as[j].getW();
p[as[j].getV()] = as[j].getU();
}
}
}
for (int j = 0; j < as.length; j++) {
if (d[as[j].getV()] > d[as[j].getU()] + as[j].getW()) {
throw new MyException("有負(fù)環(huán)");
}
}
}
}
class Adge {
private int u;
private int v;
private int w;
public Adge(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
public int getU() {
return u;
}
public void setU(int u) {
this.u = u;
}
public int getV() {
return v;
}
public void setV(int v) {
this.v = v;
}
public int getW() {
return w;
}
public void setW(int w) {
this.w = w;
}
}
c語(yǔ)言實(shí)現(xiàn)：
#include
#define MAXVALUE 10000
typedef struct node
{
int u;
int v;
int w;
};
bool BELLMAN_FORD(node G[])
{
int dis[5],pre[5],p[5];
int i,j,k;
for(i=0;i<=4;i++)
{
dis[i]=MAXVALUE;
pre[i]=-1;
p[i]=1;
}
dis[G[0].u]=0;
for(j=1;j<=4;j++)
{
for(i=0;i<=7;i++)
{
if(dis[G[i].v]>dis[G[i].u]+G[i].w)
{
dis[G[i].v]=dis[G[i].u]+G[i].w;
pre[G[i].v]=G[i].u;
}
}
}
for(i=1;i<=7;i++)
{
if(dis[G[i].v]>dis[G[i].u]+G[i].w)
return false;
}
for(i=0;i<=7;i++)
{
if(p[G[i].v]==1)
{
printf("%d %d\n",G[i].v,dis[G[i].v]);
k=G[i].v;
p[G[i].v]=0;
while(pre[k]!=-1)
{
printf("%d \n",pre[k]);
k=pre[k];
}
}
}
return true;
}
int main()
{
node G[8];
G[0].u=0;
G[0].v=1;
G[0].w=-1;
G[1].u=0;
G[1].v=2;
G[1].w=3;
G[2].u=1;
G[2].v=2;
G[2].w=3;
G[3].u=1;
G[3].v=3;
G[3].w=2;
G[4].u=1;
G[4].v=4;
G[4].w=2;
G[5].u=3;
G[5].v=1;
G[5].w=1;
G[6].u=3;
G[6].v=2;
G[6].w=5;
G[7].u=4;
G[7].v=3;
G[7].w=-3;
BELLMAN_FORD(G);
getchar();
}
//O(VE)
總結(jié)
以上是生活随笔為你收集整理的bellman ford java_Java C 实现Bellman-ford算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： mysql访问60s出现timeout_
- 下一篇： python安装poi第三方库_使用Py