All Sources Shortest Path: The Floyd-Warshall Algorithm

scvalex (Alexandru Scvortov) — Thu, 15 Nov 2007 16:19:25 GMT

This is a straightforward implementation of the Floyd-Warshall algorithm for finding the shortest path between all nodes of a graph.

A more detailed explanation is given here.



#include 



int n; /* Then number of nodes */

int dist[16][16]; /* dist[i][j] is the length of the edge between i and j if

			it exists, or 0 if it does not */



void printDist() {

	int i, j;

	printf("    ");

	for (i = 0; i < n; ++i)

		printf("%4c", 'A' + i);

	printf("\n");

	for (i = 0; i < n; ++i) {

		printf("%4c", 'A' + i);

		for (j = 0; j < n; ++j)

			printf("%4d", dist[i][j]);

		printf("\n");

	}

	printf("\n");

}



/*

	floyd_warshall()



	after calling this function dist[i][j] will the the minimum distance

	between i and j if it exists (i.e. if there's a path between i and j)

	or 0, otherwise

*/

void floyd_warshall() {

	int i, j, k;

	for (k = 0; k < n; ++k) {

		printDist();

		for (i = 0; i < n; ++i)

			for (j = 0; j < n; ++j)

				/* If i and j are different nodes and if 

					the paths between i and k and between

					k and j exist, do */

				if ((dist[i][k] * dist[k][j] != 0) && (i != j))

					/* See if you can't get a shorter path

						between i and j by interspacing

						k somewhere along the current

						path */

					if ((dist[i][k] + dist[k][j] < dist[i][j]) ||

						(dist[i][j] == 0))

						dist[i][j] = dist[i][k] + dist[k][j];

	}

	printDist();

}



int main(int argc, char *argv[]) {

	FILE *fin = fopen("dist.txt", "r");

	fscanf(fin, "%d", &n);

	int i, j;

	for (i = 0; i < n; ++i)

		for (j = 0; j < n; ++j)

			fscanf(fin, "%d", &dist[i][j]);

	fclose(fin);



	floyd_warshall();



	return 0;

}

Camino mas corto

jcongote (John Edgar Congote Calle) — Fri, 22 Sep 2006 20:15:34 GMT

Ejemplo en java del algoritmo para hallar el camino mas corto de un grafo. se implementa el algoritmo de floyd



import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;



public final class Grafo {



	private int nnodos;



	private int nodos[][][];



	private char nombres[];



	Grafo(int n) {

		this.nnodos = n;

		this.nodos = new int[nnodos][nnodos][2];

		this.nombres = new char[nnodos];

	}



	public void ingresarArco(int n1, int n2, int peso) {

		this.nodos[n1][n2][0] = peso;

		this.nodos[n2][n1][0] = peso;

		this.nodos[n1][n2][1] = n1;

		this.nodos[n2][n1][1] = n2;

	}



	public void ingresarNombre(int nodo, char letra) {

		this.nombres[nodo] = letra;

	}



	public void calcular() {

		int i, j, k;

		for (i = 0; i < this.nnodos; i++) {

			for (j = 0; j < this.nnodos; j++) {

				for (k = 0; k < this.nnodos; k++) {

					if (this.nodos[i][k][0] + this.nodos[k][j][0] < this.nodos[i][j][0]) {

						this.nodos[i][j][0] = this.nodos[i][k][0]

								+ this.nodos[k][j][0];

						this.nodos[i][j][1] = k;

					}

				}

			}

		}

	}



	public int pesominimo(int org, int des) {

		return this.nodos[org][des][0];

	}



	public String caminocorto(int org, int des) {

		String cam;

		if (org == des) {

			cam = "->" + nombres[org];

		} else {

			cam = caminocorto(org, this.nodos[org][des][1]) + "->"

					+ nombres[des];

		}

		return cam;

	}



	public char getNombre(int nodo) {

		return this.nombres[nodo];

	}



	public static void main(String args[]) throws IOException {

		Grafo g;



		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String temp;

		int res;



		System.out.println("Entre el numero de nodos del grafo:\n");

		temp = br.readLine();

		res = Integer.parseInt(temp);



		g = new Grafo(res);



		for (int i = 0; i < res; i++) {

			System.out.println("Cual es el nombre del nodo [" + (i + 1)

					+ "]:\n");

			temp = br.readLine();

			g.ingresarNombre(i, temp.charAt(0));

		}

		for (int i = 0; i < res; i++) {

			for (int j = 0; j < res; j++) {

				if (i < j) {

					System.out.println("El nodo " + g.getNombre(i)

							+ " esta conectado con el nodo " + g.getNombre(j)

							+ " (s/n)\n");

					temp = br.readLine();

					if (temp.charAt(0) == 's') {

						int peso;

						System.out.println("Cual es el peso del arco:\n");

						temp = br.readLine();

						peso = Integer.parseInt(temp);

						g.ingresarArco(i, j, peso);

					} else {

						g.ingresarArco(i, j, 10000);

					}

				}

			}

		}



		g.calcular();

		for (int i = 0; i < res; i++) {

			for (int j = 0; j < res; j++) {

				if (i > j) {

					System.out.println("El camino mas corto entre los nodos:"

							+ g.getNombre(i) + "-" + g.getNombre(j) + " es: \n"

							+ g.caminocorto(i, j) + " y su peso es: "

							+ g.pesominimo(i, j));

				}

			}

		}

	}

}

DZone Snippets: floyd code

All Sources Shortest Path: The Floyd-Warshall Algorithm

Camino mas corto