SPFA+Dijkstra+Floyd Java模板
SPFA
作者：一生何求L。
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class SPFA {
static SE[] e = new SE[9999];
static int[] dis = new int[9999];
static int[] head = new int[9999];
static boolean[] vis = new boolean[9999];
static int[] cnt = new int[9999]; //表示到达i点经历的点的个数 用来判断是否存在环
static int n,m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true) {
n = sc.nextInt();
m = sc.nextInt();
if(n==0&&m==0) break;
Arrays.fill(e, null);
Arrays.fill(head, 0);
int len = 1;
for(int i=0;i<m;i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
e[len] = new SE();
e[len].add(b, c, head[a]);
head[a] = len++;
e[len] = new SE();
e[len].add(a, c, head[b]);
head[b] = len++;
}
if(!spfa(1)) {
System.out.println("YES"+dis[n]);
}else {
System.out.println("NO");
}
}
}
public static boolean spfa(int s) {
Arrays.fill(vis, false);
Arrays.fill(dis, 99999);
Arrays.fill(cnt, 0);
dis[s] = 0;
Queue q = new LinkedList();
q.offer(s);
while(!q.isEmpty()){
int u = q.poll();
vis[u] = false;
for(int i=head[u];i!=0;i=e[i].next) {
int v = e[i].v;
int w = e[i].w+dis[u];
if(dis[v]>w) {
dis[v] = w;
cnt[v] = cnt[u]+1;
if(cnt[v]>=n) return true; //表示存在环
if(!vis[v]) {
vis[v] = true;
q.offer(v);
}
}
}
}
return false;
}
}
class SE{
int v,w,next;
public void add(int v,int w,int next) {
this.v = v;
this.w = w;
this.next = next;
}
}
Dijkstra
import java.util.Arrays;
import java.util.Scanner;
public class Dijkstra {
static int[] dis;
static int[][] G;
static int n,m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true) {
n = sc.nextInt();
m = sc.nextInt();
if(n==0&&m==0) break;
G = new int[n+1][n+1];
for(int i=1;i<=n;i++) {
Arrays.fill(G[i], 99999);
}
for(int i=0;i<m;i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
G[a][b] = G[b][a] = Math.min(G[a][b], c);
}
dis = new int[n+1];
dijkstra(1);
System.out.println(dis[n]);
}
}
public static void dijkstra(int v) {
boolean[] vis = new boolean[n+1];
for(int i=1;i<=n;i++) {
dis[i] = G[v][i];
}
dis[v] = 0;
vis[v] = true;
for(int i=1;i<=n;i++) {
int k = v;
int d = 99999;
for(int j=1;j<=n;j++) {
if(!vis[j]&&dis[j]<d) {
d = dis[j]; //找到最小的边
k = j; //对应的点
}
}
vis[k] = true;
for(int j=1;j<=n;j++) {
if(!vis[j]&&dis[k]+G[k][j]<dis[j]) {
dis[j] = dis[k]+G[k][j]; //更新经k点到j点的距离
}
}
}
}
}
Dijkstra优化
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Dijkstra优化 {
static DE[] e = new DE[9999];
static int[] dis = new int[9999];
static int[] head = new int[9999];
static boolean[] vis = new boolean[9999];
static int n,m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true) {
n = sc.nextInt();
m = sc.nextInt();
if(n==0&&m==0) break;
Arrays.fill(e, null);
Arrays.fill(head, 0);
int len = 1;
for(int i=0;i<m;i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
e[len] = new DE();
e[len].add(b, c, head[a]);
head[a] = len++;
e[len] = new DE();
e[len].add(a, c, head[b]);
head[b] = len++;
}
dijkstra(1);
System.out.println(dis[n]);
}
}
public static boolean dijkstra(int s) {
Arrays.fill(vis, false);
Arrays.fill(dis, 99999);
dis[s] = 0;
PriorityQueue q = new PriorityQueue(); //权值小的边在前
q.offer(new node(s,0));
while(!q.isEmpty()){
int u = q.poll().v;
if(vis[u]) continue;
vis[u] = true;
for(int i=head[u];i!=0;i=e[i].next) {
int v = e[i].v;
int w = e[i].w+dis[u];
if(!vis[v]&&dis[v]>w) {
dis[v] = w;
q.offer(new node(v,dis[v]));
}
}
}
return false;
}
}
class DE{
int v,w,next;
public void add(int v,int w,int next) {
this.v = v;
this.w = w;
this.next = next;
}
}
class node implements Comparable{
int v,d;
public node(int v,int d) {
this.v = v;
this.d = d;
}
@Override
public int compareTo(node o) {
// TODO Auto-generated method stub
return this.d-o.d;
}
}
Floyd
import java.util.Arrays;
import java.util.Scanner;
public class Floyd {
static int[][] G;
static int n,m;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true) {
n = sc.nextInt();
m = sc.nextInt();
if(n==0&&m==0) break;
G = new int[n+1][n+1];
for(int i=1;i<=n;i++) {
Arrays.fill(G[i], 99999);
}
for(int i=0;i<m;i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
G[a][b] = G[b][a] = Math.min(G[a][b], c);
}
floyd();
for(int i=1;i<=n;i++) {
for(int j=1;j"+j+" "+G[i][j]);
}
}
}
}
public static void floyd() {
for(int k=1;k<=n;k++) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
G[i][j] = Math.min(G[i][j], G[i][k]+G[k][j]);
}
}
}
}
}
作者：一生何求L。
