Javascript AC solution with Floyd Warshall


  • 0
    B

    It is pretty straight, build the graph and then find the path

    var dict = {};
    var graph = [];
    var res = [];
    
    for (var i = 0; i < equations.length; i++){
    
    	if ( !dict.hasOwnProperty(equations[i][0])) {
    		dict[equations[i][0]] = Object.keys(dict).length;
    	};
    
    	if ( !dict.hasOwnProperty(equations[i][1])) {
    		dict[equations[i][1]] = Object.keys(dict).length;
    
    	};
    
    	var x = dict[equations[i][0]];
    	var y = dict[equations[i][1]];
    
    
    	graph[x] = graph[x] ? graph[x] : [];
    	graph[y] = graph[y] ? graph[y] : [];
    
    	graph[x][y] = values[i];
    	graph[y][x] = 1 / values[i];
    };
    
    var len = Object.keys(dict).length;
    floyd();
    
    for (var i = 0; i < queries.length; i++) {
    	if (dict[queries[i][0]] == null || dict[queries[i][1]] == null){
    		res.push(-1.0);
    	} else if (queries[i][0] == queries[i][1]){
    		res.push(1.0);
    	} else {
        	var start = dict[queries[i][0]], end = dict[queries[i][1]];
        	if (graph[start][end]) {
        		res.push(graph[start][end]);
        	} else {
        		res.push(-1.0);
        	}
       }
    };
    // --Floyd Warshall---
    function floyd () {
    	for (var i = 0; i < len; i++) {
    		for (var j = 0; j < len; j++) {
    			for (var k = 0; k < len; k++) {
    				if (graph[j][i] != null && graph[i][k] != null && !graph[j][k]) {
    					graph[j][k] = graph[j][i] * graph[i][k];
    				}
    			}	
    		}
    	}
    };
    
    return res;

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.