本文共 1882 字，大约阅读时间需要 6 分钟。

一、Edge边表示、判断负环

       注意这里的图一般用有向图表示 也就是说 1 - 2， 2 - 1 如果权重为负值  那么 也算有负权环（这里表示了添加两条边的方法）

       这里因为添加双向边 则 一旦有负w出现就会认为是负权环

import java.util.Scanner;public class Main {	static Edge []edges;	static boolean []visit;	static int n, m;	static int tol;	static int[]dis;	static int INF = 9999999;	static int[]head;	static boolean hasNegCycle = false;	public static void main(String[] args) {		Scanner in = new Scanner(System.in);		while(in.hasNext()) {			n = in.nextInt();			m = in.nextInt();			if(n == 0 && m == 0)				break;			edges = new Edge[2*m+1];			for(int i = 1; i <= 2*m; i++ )				edges[i] = new Edge();			tol = 1;			head = new int[n+1];			dis = new int[n+1];			for(int i = 1; i <= n; i++ )				head[i] = -1;			for(int i = 1; i <= m; i++ ) {				int u = in.nextInt();				int v = in.nextInt();				int w = in.nextInt();				add(u, v, w);				add(v, u, w);			}			bell_man();			if(!hasNegCycle) {				System.out.println(dis[n]);			}			else				System.out.println("hasNegtiveCycle");//			for(int i = 1; i < tol; i++ ) {//				Edge e = edges[i];//				System.out.println(e.from + " " + e.to + " " + e.w);//			}		}			}	public static void bell_man() {				for(int i = 1; i <= n; i++ ) {			dis[i] = (i == 1) ? 0 : INF;		}				for(int i = 1; i < n; i++ ) {			int flag = 0;			for(int j = 1; j <= 2*m; j++ ) {				Edge e = edges[j];				if(dis[e.to] > dis[e.from] + e.w) {					flag = 1;					dis[e.to] = dis[e.from] + e.w;				}			}			if(flag == 0)				break;		}		hasNegCycle = false;		for(int i = 1; i <= 2*m; i++ ) {			Edge e = edges[i];			if(dis[e.to] > dis[e.from] + e.w) {				hasNegCycle = true;				break;			}		}	}	public static void add(int from, int to, int w) {		edges[tol].from = from;		edges[tol].to = to;		edges[tol].w = w;		edges[tol].next = head[from];		head[from] = tol++;	}}class Edge{	int from, to;	int w;	int next;//	public Edge(int from, int to) {//		this.from = from;//		this.to = to;//		this.w = w;//	}}

转载地址：http://alimi.baihongyu.com/